CSES - Putka Open 2015 – 4/6 - Results
Submission details
Task:Taulukot
Sender:
Submission time:2015-10-11 20:08:19 +0300
Language:C++
Status:READY
Result:55
Feedback
groupverdictscore
#1ACCEPTED26
#2ACCEPTED29
#30
Test results
testverdicttimegroup
#1ACCEPTED0.06 s1details
#2ACCEPTED0.05 s1details
#3ACCEPTED0.05 s1details
#4ACCEPTED0.06 s1details
#5ACCEPTED0.06 s1details
#6ACCEPTED0.06 s2details
#7ACCEPTED0.06 s2details
#8ACCEPTED0.05 s2details
#9ACCEPTED0.06 s2details
#10ACCEPTED0.06 s2details
#11ACCEPTED0.07 s3details
#120.08 s3details
#13ACCEPTED0.08 s3details
#14ACCEPTED0.07 s3details
#15ACCEPTED0.07 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < prime.size(); j++){
                    ^

Code

#include <bits/stdc++.h>

#define i64 long long
#define u64 unsigned long long
#define i32 int
#define u32 unsigned int

#define pii pair<int, int>
#define pll pair<long long, long long>

#define defmod 1000000007
using namespace std;
bool sieve[1010101] = {0};
vector<int> prime;
void eratosthenes(int n)
{
  
  sieve[0] = 1; sieve[1] = 1;
  int m = (int) sqrt((double) n);

  for(int i = 0; i <= m; i++) {
    if(!sieve[i]) {
    	//prime.push_back(i);
      for (int j = i*i; j <= n; j += i)
        sieve[j] = 1;
    }
  }
  
}

int main(){
	srand (time(NULL));
	cin.sync_with_stdio(0);
	cin.tie(0);
	eratosthenes(200010);
	for(int i = 2; i <= 200000; i++){
		if(sieve[i] == 0)
			prime.push_back(i);
	}
	int n; cin >> n;
	vector<int> a1, b1;

	unordered_set<int> a;
	for(int i = 1; i < n; i++)
		a.insert(i+1);
	random_shuffle(prime.begin(), prime.end());
	//cout << prime.size() << " primeja" << endl;
	int lell = 1;
	bool d[101010] = {0};
	if(n%2 == 1){
		a1.push_back(1);
		b1.push_back(1);
	}
	else{
		a.insert(1);
		lell = 0;
	}

	for(int i = n; i > lell; i--){
		if(d[i])
			continue;
		
		//cout << "lb " << *lower_bound(prime.begin(), prime.end(), i) << endl;
		for(int j = 0; j < prime.size(); j++){
			if(a.count(prime[j]-i)){
				//cout << i  << "+" << prime[j]-i << " = " << prime[j] << endl;
				a1.push_back(i);
				b1.push_back(prime[j]-i);
				if(i != prime[j]-i){
					a1.push_back(prime[j]-i);
					b1.push_back(i);
				}
				a.erase(prime[j]-i);
				a.erase(i);
				//cout << i << " ja " << prime[j]-i << endl;
				
				d[prime[j]-i] = true;

				break;
			}
		}
		
	}
	
	
	for(int i = 0; i < n; i++)
		cout << a1[i] << " ";
	cout << endl;
	for(int i = 0; i < n; i++)
		cout << b1[i] << " ";
	cout << endl;
	return 0;
	
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
1

correct output


user output


Test 2

Group: 1

Verdict: ACCEPTED

input
4

correct output
1 2 3 4 
2 1 4 3 

user output
4 3 2 1 
3 4 1 2 

Test 3

Group: 1

Verdict: ACCEPTED

input
5

correct output
1 2 3 4 5 
1 5 4 3 2 

user output
1 5 2 4 3 
1 2 5 3 4 

Test 4

Group: 1

Verdict: ACCEPTED

input
8

correct output
1 2 3 4 5 6 7 8 
2 1 4 3 8 7 6 5 

user output
8 5 7 6 4 1 3 2 
5 8 6 7 1 4 2 3 

Test 5

Group: 1

Verdict: ACCEPTED

input
9

correct output
1 2 3 4 5 6 7 8 9 
1 5 4 3 2 7 6 9 8 

user output
1 9 8 7 6 5 2 4 3 
1 8 9 6 7 2 5 3 4 

Test 6

Group: 2

Verdict: ACCEPTED

input
77

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
1 77 6 76 7 75 8 74 9 73 10 72...

Test 7

Group: 2

Verdict: ACCEPTED

input
70

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
70 13 69 14 68 15 67 16 66 1 6...

Test 8

Group: 2

Verdict: ACCEPTED

input
72

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
72 25 71 26 70 27 69 28 68 29 ...

Test 9

Group: 2

Verdict: ACCEPTED

input
86

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
86 71 85 72 84 73 83 74 82 75 ...

Test 10

Group: 2

Verdict: ACCEPTED

input
68

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
68 59 67 60 66 61 65 62 64 63 ...

Test 11

Group: 3

Verdict: ACCEPTED

input
90764

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
90764 42129 90763 42130 90762 ...

Test 12

Group: 3

Verdict:

input
97976

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
97976 60365 97975 60366 97974 ...

Test 13

Group: 3

Verdict: ACCEPTED

input
96762

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
96762 61579 96761 61580 96760 ...

Test 14

Group: 3

Verdict: ACCEPTED

input
94823

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
1 94823 83144 94822 83145 9482...

Test 15

Group: 3

Verdict: ACCEPTED

input
91479

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
1 91479 19150 91478 19151 9147...