CSES - Putka Open 2020 – 1/5 - Results
Submission details
Task:Lista
Sender:rasastusni
Submission time:2020-09-06 20:37:13 +0300
Language:C++ (C++17)
Status:READY
Result:59
Feedback
groupverdictscore
#1ACCEPTED21
#2ACCEPTED38
#30
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
#16--3details
#17ACCEPTED0.02 s3details
#18--3details
#19--3details
#20--3details
#21ACCEPTED0.01 s3details

Code

#include <iostream>
using namespace std;
const int MAX_N = 1000;
int numbers[MAX_N] = {0};
int can_use[MAX_N] = {0};
int prime_cache[2*MAX_N] = {0};
int target = 0;
int is_prime(int x) {
if (x == 0 || x == 1) return 0;
if (x == 2 || x == 3) return 1;
if (prime_cache[x] > 0) {
return prime_cache[x] - 1;
}
int y = 2;
while (y*y <= x) {
if (x%y == 0) {
prime_cache[x] = 1;
return 0;
}
++y;
}
prime_cache[x] = 2;
return 1;
}
int solve(int depth)
{
if (depth == target) {
return 1;
}
for (int i = 0; i < target; ++i) {
if (can_use[i]) {
if (depth == 0 || is_prime(i + 1 + numbers[depth - 1])) {
can_use[i] = 0;
numbers[depth] = i + 1;
int succ = solve(depth + 1);
if (succ) return 1;
numbers[depth] = 0;
can_use[i] = 1;
}
}
}
return 0;
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
can_use[i] = 1;
}
target = n;
solve(0);
for (int i = 0; i < n - 1; ++i) {
cout << numbers[i] << " ";
}
cout << numbers[n - 1] << endl;
}

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 2 3 4

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
5

correct output
3 4 1 2 5 

user output
1 4 3 2 5

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
6

correct output
3 4 1 2 5 6 

user output
1 4 3 2 5 6

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 4 7 6 5 8

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 3 4 7 6 5 8 9

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 2 3 4 7 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
1 2 3 4 7 6 5 8 9 10 13 16 15 ...

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 4 7 6 5 8 9 10 13 16 15 ...
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
1 2 3 4 7 6 5 8 9 10 13 16 15 ...
Truncated

Test 13

Group: 2, 3

Verdict: ACCEPTED

input
76

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

user output
1 2 3 4 7 6 5 8 9 10 13 16 15 ...
Truncated

Test 14

Group: 2, 3

Verdict: ACCEPTED

input
90

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

user output
1 2 3 4 7 6 5 8 9 10 13 16 15 ...
Truncated

Test 15

Group: 2, 3

Verdict: ACCEPTED

input
100

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

user output
1 2 3 4 7 6 5 8 9 10 13 16 15 ...
Truncated

Test 16

Group: 3

Verdict:

input
154

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

user output
(empty)

Test 17

Group: 3

Verdict: ACCEPTED

input
430

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

user output
1 2 3 4 7 6 5 8 9 10 13 16 15 ...
Truncated

Test 18

Group: 3

Verdict:

input
629

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

user output
(empty)

Test 19

Group: 3

Verdict:

input
833

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

user output
(empty)

Test 20

Group: 3

Verdict:

input
885

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

user output
(empty)

Test 21

Group: 3

Verdict: ACCEPTED

input
1000

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

user output
1 2 3 4 7 6 5 8 9 10 13 16 15 ...
Truncated