Task: | Lista |
Sender: | Hannes |
Submission time: | 2020-09-06 17:40:04 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 21 |
#2 | ACCEPTED | 38 |
#3 | ACCEPTED | 41 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#4 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#5 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#6 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#7 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#8 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#9 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#10 | ACCEPTED | 0.01 s | 2, 3 | details |
#11 | ACCEPTED | 0.01 s | 2, 3 | details |
#12 | ACCEPTED | 0.01 s | 2, 3 | details |
#13 | ACCEPTED | 0.01 s | 2, 3 | details |
#14 | ACCEPTED | 0.01 s | 2, 3 | details |
#15 | ACCEPTED | 0.01 s | 2, 3 | details |
#16 | ACCEPTED | 0.01 s | 3 | details |
#17 | ACCEPTED | 0.01 s | 3 | details |
#18 | ACCEPTED | 0.01 s | 3 | details |
#19 | ACCEPTED | 0.02 s | 3 | details |
#20 | ACCEPTED | 0.02 s | 3 | details |
#21 | ACCEPTED | 0.03 s | 3 | details |
Compiler report
input/code.cpp: In function 'void shufflert(int)': input/code.cpp:15:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i=0;i<rt[c].size();++i) { ~^~~~~~~~~~~~~ input/code.cpp: In function 'void addnxt(int)': input/code.cpp:31:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i=0;i<rt[c].size();++i) { ~^~~~~~~~~~~~~
Code
#include <bits/stdc++.h>using namespace std;int n;const int N=2020;int p[N];vector<int> rt[1010];int prv[1010];int nxt[1010];deque<int> znxt;void shufflert(int c) {for (int i=0;i<rt[c].size();++i) {swap(rt[c][i], rt[c][rand()%(i+1)]);}}bool find(int a, int b) {while (nxt[a] && a!=b) a=nxt[a];return a==b;}void addnxt(int c) {if (!rt[c].size()) {znxt.push_back(c);return;}shufflert(c);for (int i=0;i<rt[c].size();++i) {int w=rt[c][i];if (find(w, c)) continue;nxt[c]=w;if (prv[w]) {nxt[prv[w]]=0;znxt.push_back(prv[w]);}prv[nxt[c]]=c;return;}znxt.push_back(c);}bool solve(int n) {for (int i=1;i<=n;++i) rt[i].clear(), nxt[i]=0, prv[i]=0;for (int i=1;i<=n;++i) {for (int j=i+1;j<=n;++j) {if (!p[i+j]) {rt[i].push_back(j);rt[j].push_back(i);}}}znxt.clear();for (int i=1;i<=n;++i) addnxt(i);int loops=0;while (znxt.size()>1 && ++loops<10000) {int c=znxt.front();znxt.pop_front();if (nxt[c]) continue;addnxt(c);}// for (int i=1;i<=n;++i) cout << nxt[i] << " ";cout << endl;// for (int i=1;i<=n;++i) cout << prv[i] << " ";cout << endl;int c=znxt.size()?znxt.front():1;for (int i=0;i<n;++i) {cout << c << " ";c=prv[c];}cout << endl;return 1;}int main() {p[0]=1;p[1]=1;for (int i=2;i<N;++i) {if (p[i]) continue;for (int j=i+i;j<N;j+=i) p[j]=1;}/*for (int i=1;i<1000;++i) {if (!solve(i)) { cout << "QAQ\n" << endl; return 0;}cout << i << endl;}return 0;//*/cin >> n;if (!solve(n)) cout << "QAQ\n" << endl;}
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
2 |
correct output |
---|
1 2 |
user output |
---|
2 1 |
Test 2
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
3 |
correct output |
---|
1 2 3 |
user output |
---|
3 2 1 |
Test 3
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
4 |
correct output |
---|
1 2 3 4 |
user output |
---|
4 1 2 3 |
Test 4
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
5 |
correct output |
---|
3 4 1 2 5 |
user output |
---|
5 2 1 4 3 |
Test 5
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
6 |
correct output |
---|
3 4 1 2 5 6 |
user output |
---|
2 5 6 1 4 3 |
Test 6
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
7 |
correct output |
---|
3 4 1 2 5 6 7 |
user output |
---|
1 6 5 2 3 4 7 |
Test 7
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
8 |
correct output |
---|
7 6 5 2 1 4 3 8 |
user output |
---|
8 3 4 7 6 1 2 5 |
Test 8
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
9 |
correct output |
---|
7 6 5 2 1 4 3 8 9 |
user output |
---|
9 4 1 2 3 8 5 6 7 |
Test 9
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
10 |
correct output |
---|
7 6 5 2 1 4 3 8 9 10 |
user output |
---|
7 4 3 2 1 6 5 8 9 10 |
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 |
---|
13 16 3 14 9 2 15 4 19 10 7 12... |
Test 11
Group: 2, 3
Verdict: ACCEPTED
input |
---|
56 |
correct output |
---|
55 54 53 50 51 52 49 48 13 28 ... |
user output |
---|
53 30 41 32 11 12 55 18 13 6 1... Truncated |
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 |
---|
53 18 23 20 51 58 31 30 43 10 ... Truncated |
Test 13
Group: 2, 3
Verdict: ACCEPTED
input |
---|
76 |
correct output |
---|
73 66 61 42 59 54 53 50 51 52 ... |
user output |
---|
6 1 30 31 42 11 60 7 4 55 48 2... Truncated |
Test 14
Group: 2, 3
Verdict: ACCEPTED
input |
---|
90 |
correct output |
---|
87 86 11 18 29 44 45 16 55 58 ... |
user output |
---|
16 15 14 83 90 41 48 55 52 87 ... Truncated |
Test 15
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 |
correct output |
---|
97 96 95 78 25 82 81 56 71 68 ... |
user output |
---|
64 73 58 43 30 97 42 17 92 35 ... Truncated |
Test 16
Group: 3
Verdict: ACCEPTED
input |
---|
154 |
correct output |
---|
151 6 5 92 137 134 149 84 143 ... |
user output |
---|
37 30 151 142 97 54 35 38 69 6... Truncated |
Test 17
Group: 3
Verdict: ACCEPTED
input |
---|
430 |
correct output |
---|
427 426 371 372 367 376 375 35... |
user output |
---|
400 121 268 415 16 213 230 47 ... Truncated |
Test 18
Group: 3
Verdict: ACCEPTED
input |
---|
629 |
correct output |
---|
627 404 227 146 83 150 77 74 3... |
user output |
---|
535 304 337 484 285 434 165 43... Truncated |
Test 19
Group: 3
Verdict: ACCEPTED
input |
---|
833 |
correct output |
---|
829 828 793 574 523 516 515 51... |
user output |
---|
523 708 25 154 519 568 219 350... Truncated |
Test 20
Group: 3
Verdict: ACCEPTED
input |
---|
885 |
correct output |
---|
883 724 723 878 881 726 721 71... |
user output |
---|
755 56 383 230 443 434 107 666... Truncated |
Test 21
Group: 3
Verdict: ACCEPTED
input |
---|
1000 |
correct output |
---|
997 996 737 884 995 492 991 20... |
user output |
---|
598 135 146 33 26 621 208 385 ... Truncated |