CSES - Putka Open 2020 – 1/5 - Results
Submission details
Task:Lista
Sender:tsiki2
Submission time:2020-09-06 20:39:46 +0300
Language:C++ (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.01 s3details
#20ACCEPTED0.01 s3details
#21ACCEPTED0.01 s3details

Compiler report

input/code.cpp: In function 'bool isok(std::vector<int>&, int, int)':
input/code.cpp:47:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (idx == ans.size() - 1) {
      ~~~~^~~~~~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:88:6: warning: unused variable 'even_idx' [-Wunused-variable]
  int even_idx = (n%2) ? n-2 : n-1;
      ^~~~~~~~

Code

#include <stdio.h> // include before iostream for faster scanf
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <set>
#include <unordered_set>
#include <cmath>
#include <math.h>
#include <queue>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <tuple>
#include <utility>
#include <iomanip>
#include <iterator>
using namespace std;
typedef long long LL;
#define printv(printVec) for (auto printVecIter : (printVec)) cout << printVecIter << " "; cout << endl;
// g++ -Wall -Wshadow -std=c++11 a.cpp && ./a.out
vector<bool> PRIMES;
void get_primes() {
vector<bool> ans(3000);
for (int i = 2; i < 3000; i++) {
bool isp = true;
for (int j = 2; j*j <= i; j++) {
if ((i % j) == 0) isp = false;
}
ans[i] = isp;
}
PRIMES = ans;
}
bool isok(vector<int> & ans, int idx, int newnum) {
if (idx == 0) {
return PRIMES[newnum + ans[0]];
}
if (idx == ans.size() - 1) {
return PRIMES[ans[ans.size() - 2] + newnum] && PRIMES[ans[ans.size() - 2] + newnum + 2];
}
return PRIMES[ans[idx-1]+newnum] && PRIMES[newnum+ans[idx+1]];
}
void do_shit(set<int> & unused, vector<int> & ans) {
auto it = unused.begin();
int smallest = *it;
int idx = ans.size() - 1;
while (ans[idx] != 0) {
idx--;
}
while (!isok(ans, idx, *it)) {
it++;
}
auto begin = it;
while (it != unused.end()) {
smallest = *it;
ans[idx] = smallest;
idx -= 2;
it++;
}
unused.erase(begin, unused.end());
}
int main() {
std::ios::sync_with_stdio(false);cin.tie(0);
int n; cin >> n;
get_primes();
vector<int> ans(n);
for (int i = 1; i <= n; i += 2) {
ans[i-1] = i;
}
int even_idx = (n%2) ? n-2 : n-1;
set<int> unused;
for (int i = 2; i <= n; i += 2) {
unused.insert(i);
}
while (unused.size()) {
do_shit(unused, ans);
}
for (auto i : ans) {
cout << i << " ";
}
}
/*
1 (2) 3 (8) 5 (6) 7 (4,6)
1 (2,4) 3 (2,8) 5 (2,6)
*/

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

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 3 8 5 6 7 4 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 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 10 3 8 5 6 7 4 9 2 11 18 13 ...

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 ...
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 70 3 68 5 66 7 64 9 62 11 60...
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 4 3 2 5 24 7 22 9 20 11 18 1...
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 10 3 8 5 6 7 4 9 2 11 90 13 ...
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 100 3 98 5 96 7 94 9 92 11 9...
Truncated

Test 16

Group: 3

Verdict: ACCEPTED

input
154

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

user output
1 4 3 2 5 24 7 22 9 20 11 18 1...
Truncated

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

Test 18

Group: 3

Verdict: ACCEPTED

input
629

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

user output
1 4 3 2 5 12 7 10 9 8 11 6 13 ...
Truncated

Test 19

Group: 3

Verdict: ACCEPTED

input
833

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

user output
1 4 3 2 5 24 7 22 9 20 11 18 1...
Truncated

Test 20

Group: 3

Verdict: ACCEPTED

input
885

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

user output
1 2 3 134 5 132 7 130 9 128 11...
Truncated

Test 21

Group: 3

Verdict: ACCEPTED

input
1000

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

user output
1 10 3 8 5 6 7 4 9 2 11 18 13 ...
Truncated