CSES - Putka Open 2020 – 1/5

Submission details
Task:	Lista
Sender:	kluopaja
Submission time:	2020-09-06 14:00:41 +0300
Language:	C++ (C++11)
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	21
#2	ACCEPTED	38
#3	ACCEPTED	41

Test results
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.02 s	3	details
#18	ACCEPTED	0.03 s	3	details
#19	ACCEPTED	0.04 s	3	details
#20	ACCEPTED	0.05 s	3	details
#21	ACCEPTED	0.06 s	3	details

Compiler report

input/code.cpp: In function 'int check(int, std::vector<int>&)':
input/code.cpp:8:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(pos+1 == v.size()) {
        ~~~~~~^~~~~~~~~~~
input/code.cpp: In function 'int sum(std::vector<int>&)':
input/code.cpp:15:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i+1 < v.size(); ++i) {
                    ~~~~^~~~~~~~~~

Code

#include <bits/stdc++.h>
using namespace std;
bool is_prime[2000];
int check(int pos, vector<int> & v) {
    if(pos == 0) {
        return is_prime[v[0]+v[1]];
    }
    if(pos+1 == v.size()) {
        return is_prime[v[pos-1]+v[pos]];
    }
    return int(is_prime[v[pos-1]+v[pos]]) + int(is_prime[v[pos]+v[pos+1]]);
}
int sum(vector<int> & v) {
    int s = 0;
    for(int i = 0; i+1 < v.size(); ++i) {
        s += is_prime[v[i]+v[i+1]];
    }
    return s;
}
vector<int> brute(int n) {
    vector<int> v(n);
    for(int i = 0; i < n; ++i) {
        v[i] = i+1;
    }
    mt19937 mt(1337);
    while(1) {
        int ok = 1;
        for(int i = 0; i+1 < n; ++i) {
            if(!is_prime[v[i]+v[i+1]]) {
                ok = 0;
            }
        }
        if(ok) return v;
        ok = 0;

        for(int i = 0; i+1 < n; ++i) {
            for(int j = 0; j < n; ++j) {
                int x = v[j]-1;
                int prev = check(i, v) + check(x, v);
                swap(v[i], v[x]);
                int curr = check(i, v) + check(x, v);
                if(curr > prev) {
                    ok = 1;
                    break;
                }
                swap(v[i], v[x]);
            }
        }
        for(int i = 0; i+1 < n; ++i) {
            for(int j = 0; j < n; ++j) {
                int x = v[j]-1;
                int prev = check(i, v) + check(x, v);
                swap(v[i], v[x]);
                int curr = check(i, v) + check(x, v);
                if(curr == prev) {
                    ok = 1;
                    break;
                }
                swap(v[i], v[x]);
            }
        }
        if(!ok) {
            uniform_int_distribution<int> dist(0, n-1);
            swap(v[dist(mt)], v[dist(mt)]);
        }
    };
    return {-1};
}
int main() {
    for(int i = 2; i < 2000; ++i) is_prime[i] = 1;
    for(int i = 2; i*i < 2000; ++i) {
        for(int j = i*i; j < 2000; j += i) {
            is_prime[j] = 0;
        }
    }
    int n;
    cin>>n;
    auto v  = brute(n);
    for(auto x: v) {
        cout<<x<<' ';
    }
    cout<<'\n';
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
`2` view save

correct output
`1 2` view save

user output
`1 2` view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
`3` view save

correct output
`1 2 3` view save

user output
`1 2 3` view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
`4` view save

correct output
`1 2 3 4` view save

user output
`1 2 3 4` view save

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
`5` view save

correct output
`3 4 1 2 5` view save

user output
`5 2 1 4 3` view save

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`6` view save

correct output
`3 4 1 2 5 6` view save

user output
`5 2 3 4 1 6` view save

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
`7` view save

correct output
`3 4 1 2 5 6 7` view save

user output
`5 2 3 4 1 6 7` view save

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
`8` view save

correct output
`7 6 5 2 1 4 3 8` view save

user output
`3 2 1 4 7 6 5 8` view save

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
`9` view save

correct output
`7 6 5 2 1 4 3 8 9` view save

user output
`3 2 9 8 5 6 7 4 1` view save

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
`10` view save

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

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

Test 10

Group: 2, 3

Verdict: ACCEPTED

input
`19` view save

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

user output
`9 4 13 10 1 18 5 2 15 16 7 6 1...` view save

Test 11

Group: 2, 3

Verdict: ACCEPTED

input
`56` view save

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

user output
`49 10 51 22 1 36 37 42 47 50 9...` Truncated

Test 12

Group: 2, 3

Verdict: ACCEPTED

input
`70` view save

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

user output
`53 36 37 64 67 16 15 32 41 60 ...` Truncated

Test 13

Group: 2, 3

Verdict: ACCEPTED

input
`76` view save

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

user output
`11 36 67 22 25 18 29 2 41 32 9...` Truncated

Test 14

Group: 2, 3

Verdict: ACCEPTED

input
`90` view save

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

user output
`79 70 37 24 73 84 53 44 87 50 ...` Truncated

Test 15

Group: 2, 3

Verdict: ACCEPTED

input
`100` view save

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

user output
`35 78 49 22 31 58 39 98 3 100 ...` Truncated

Test 16

Group: 3

Verdict: ACCEPTED

input
`154` view save

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

user output
`51 58 79 30 73 138 101 66 41 7...` Truncated

Test 17

Group: 3

Verdict: ACCEPTED

input
`430` view save

correct output
`427 426 371 372 367 376 375 35...` view save

user output
`27 412 375 196 291 26 323 410 ...` Truncated

Test 18

Group: 3

Verdict: ACCEPTED

input
`629` view save

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

user output
`423 334 145 138 13 268 613 28 ...` Truncated

Test 19

Group: 3

Verdict: ACCEPTED

input
`833` view save

correct output
`829 828 793 574 523 516 515 51...` view save

user output
`461 636 487 442 129 434 753 54...` Truncated

Test 20

Group: 3

Verdict: ACCEPTED

input
`885` view save

correct output
`883 724 723 878 881 726 721 71...` view save

user output
`801 136 603 526 117 20 39 298 ...` Truncated

Test 21

Group: 3

Verdict: ACCEPTED

input
`1000` view save

correct output
`997 996 737 884 995 492 991 20...` view save

user output
`965 534 277 442 379 124 225 68...` Truncated

Putka Open 2020 – 1/5

Lista

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Tasks

Submissions (kluopaja)