CSES - Putka Open 2020 – 1/5 - Results
Submission details
Task:Lista
Sender:Hannes
Submission time:2020-09-06 17:40:04 +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.01 s3details
#19ACCEPTED0.02 s3details
#20ACCEPTED0.02 s3details
#21ACCEPTED0.03 s3details

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...

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 ...

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...

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 ...

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 ...

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...

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 ...

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...

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...

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...

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 ...