CSES - Putka Open 2020 – 1/5 - Results
Submission details
Task:Lista
Sender:Guuber
Submission time:2020-09-05 10:20:27 +0300
Language:C++11
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED21
#2ACCEPTED38
#3ACCEPTED41
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.01 s1, 2, 3details
#7ACCEPTED0.01 s1, 2, 3details
#8ACCEPTED0.01 s1, 2, 3details
#9ACCEPTED0.01 s1, 2, 3details
#10ACCEPTED0.01 s2, 3details
#11ACCEPTED0.01 s2, 3details
#12ACCEPTED0.01 s2, 3details
#13ACCEPTED0.01 s2, 3details
#14ACCEPTED0.01 s2, 3details
#15ACCEPTED0.01 s2, 3details
#16ACCEPTED0.01 s3details
#17ACCEPTED0.01 s3details
#18ACCEPTED0.02 s3details
#19ACCEPTED0.51 s3details
#20ACCEPTED0.01 s3details
#21ACCEPTED0.01 s3details

Compiler report

input/code.cpp: In function 'void haku(int, std::vector<int>)':
input/code.cpp:23:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(path.size() == n){
     ~~~~~~~~~~~~^~~~

Code

#include<bits/stdc++.h>
using namespace std;

vector<int> graph[101010];
int prime[1010101];
int degree[101010];
int z[101010];
int eka[101010];
int toka[101010];
int kaytetty[101010];
vector<int> polku;


int n;
bool bo;
void haku(int node, vector<int> path){
	//cout << path.size() << "\n";
	if(z[node]) return;
	if(bo) return;
	z[node] = 1;
	path.push_back(node);
	//cout << path.size() << " " << n << "\n";
	if(path.size() == n){
		//	cout << "LOIJOIJOIJOIJOIJOJOJOIJO\n";
		polku = path;
		bo = true;
		return;
	}
	degree[node]--;
	vector<pair<int,int>> seuri;
	for(auto seur : graph[node]){
		if(bo) return;
		//		haku(seur, path);
		seuri.push_back({degree[seur], seur});
	}
	sort(seuri.begin(), seuri.end());

	for(auto u : seuri){
		if(u.first > 1){
			if(bo) return;
			degree[u.second]--;
			haku(u.second, path);
			degree[u.second]++;
		}
	}
	degree[node]++;
	z[node] = 0;
}

int main(){
//	cin >> n;

	cin >> n;
	for(int i = 2; i < 10101; i++){
		if(prime[i]) continue;
		prime[i] = i;
		for(int u = i; u <= 10101; u += i){
			prime[u] = i;
		}
	}

	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(prime[i+j] == i+j){
				degree[i]++;
				degree[j]++;
				graph[i].push_back(j);
				graph[j].push_back(i);
			}
		}
	}


	int luku = n;
	while(luku != 0){
		for(int i = 1; i <= n; i++){
			if(prime[i+luku] == i+luku){
				for(int j = 0; j <= luku; j++){
					eka[luku-j] = i + j;
				}
				luku = i-1;
				break;
			}
		}
	}

	luku = n;
	while(luku != 0){
		for(int i = luku; i >= 1; i--){
			if(prime[i + luku] == i + luku){
				for(int j = 0; j <= luku; j++){
					toka[luku-j] = i + j;
				}
				luku = i-1;
				break;
			}
		}
	}

	for(int ss = 1; ss <= 2000; ss++){
		int e = ss;
		bo = true;
		vector<int> ve = {};
		for(int i = 0; i < n; i++){
			ve.push_back(e);
			if(kaytetty[e]) bo = false;
			kaytetty[e] = 1;
			if(!kaytetty[eka[e]]){
				e = eka[e];
			}else if(!kaytetty[eka[e]]){
				e = toka[e];
			}else{
				for(int i = 1; i <= n; i++){
					if(!kaytetty[i] && prime[i+e] == i+e){
						e = i;
						break;
					}
				}
			}
		}
		for(int i = 0; i <= 2000; i++){
			kaytetty[i] = 0;
		}
		if(bo){ for(auto u : ve) cout << u << " "; cout << "\n"; break;} 
		//cout << "\n\n";
		//cout << ve.size() << " SIZE\n";
	}
	if(!bo){
		haku(1,{});
		for(auto u : polku) cout << u << " ";
		cout << "\n";
	}
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
2

correct output
1 2 

user output
1 2 

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
3

correct output
1 2 3 

user output
1 2 3 

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
4

correct output
1 2 3 4 

user output
1 4 3 2 

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
5

correct output
3 4 1 2 5 

user output
3 4 1 2 5 

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
6

correct output
3 4 1 2 5 6 

user output
1 6 5 2 3 4 

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
7

correct output
3 4 1 2 5 6 7 

user output
1 2 3 4 7 6 5 

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
8

correct output
7 6 5 2 1 4 3 8 

user output
1 2 3 8 5 6 7 4 

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
9

correct output
7 6 5 2 1 4 3 8 9 

user output
1 2 9 4 7 6 5 8 3 

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
10

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

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

Test 10

Group: 2, 3

Verdict: ACCEPTED

input
19

correct output
17 14 3 8 15 16 13 6 5 2 1 4 9...

user output
1 16 7 6 17 14 9 8 11 18 19 12...

Test 11

Group: 2, 3

Verdict: ACCEPTED

input
56

correct output
55 54 53 50 51 52 49 48 13 28 ...

user output
1 2 3 56 5 54 7 52 9 50 11 48 ...

Test 12

Group: 2, 3

Verdict: ACCEPTED

input
70

correct output
67 4 1 2 9 32 35 38 65 66 61 4...

user output
1 70 3 68 5 66 7 64 9 62 11 60...

Test 13

Group: 2, 3

Verdict: ACCEPTED

input
76

correct output
73 66 61 42 59 54 53 50 51 52 ...

user output
15 64 3 76 7 72 1 2 5 74 9 70 ...

Test 14

Group: 2, 3

Verdict: ACCEPTED

input
90

correct output
87 86 11 18 29 44 45 16 55 58 ...

user output
15 82 1 6 5 2 3 4 7 90 11 86 1...

Test 15

Group: 2, 3

Verdict: ACCEPTED

input
100

correct output
97 96 95 78 25 82 81 56 71 68 ...

user output
1 100 3 98 5 96 7 94 9 92 11 9...

Test 16

Group: 3

Verdict: ACCEPTED

input
154

correct output
151 6 5 92 137 134 149 84 143 ...

user output
37 120 7 150 1 2 3 154 9 148 1...

Test 17

Group: 3

Verdict: ACCEPTED

input
430

correct output
427 426 371 372 367 376 375 35...

user output
1 430 3 428 5 426 7 424 9 422 ...

Test 18

Group: 3

Verdict: ACCEPTED

input
629

correct output
627 404 227 146 83 150 77 74 3...

user output
79 552 5 626 15 616 1 2 629 12...

Test 19

Group: 3

Verdict: ACCEPTED

input
833

correct output
829 828 793 574 523 516 515 51...

user output
1 646 763 684 593 588 709 762 ...

Test 20

Group: 3

Verdict: ACCEPTED

input
885

correct output
883 724 723 878 881 726 721 71...

user output
1 2 885 22 865 12 875 6 881 26...

Test 21

Group: 3

Verdict: ACCEPTED

input
1000

correct output
997 996 737 884 995 492 991 20...

user output
1 2 3 8 5 6 7 4 9 1000 13 996 ...