CSES - Putka Open 2020 – 1/5

Submission details
Task:	Lista
Sender:	mango_lassi
Submission time:	2020-09-04 18:42:05 +0300
Language:	C++ (C++11)
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	WRONG ANSWER	0
#2	WRONG ANSWER	0
#3	WRONG ANSWER	0

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	WRONG ANSWER	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	WRONG ANSWER	0.01 s	2, 3	details
#12	WRONG ANSWER	0.01 s	2, 3	details
#13	ACCEPTED	0.01 s	2, 3	details
#14	WRONG ANSWER	0.01 s	2, 3	details
#15	WRONG ANSWER	0.01 s	2, 3	details
#16	WRONG ANSWER	0.01 s	3	details
#17	WRONG ANSWER	0.01 s	3	details
#18	WRONG ANSWER	0.01 s	3	details
#19	WRONG ANSWER	0.03 s	3	details
#20	WRONG ANSWER	0.03 s	3	details
#21	WRONG ANSWER	0.02 s	3	details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:72:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (int& v : res) cout << v << ' '; cout << '\n';
  ^~~
input/code.cpp:72:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (int& v : res) cout << v << ' '; cout << '\n';
                                       ^~~~

Code

#include <iostream>
#include <random>
#include <chrono>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1000;
const int H = 10 * N;
bool is_prime[2*N+1];

bool recBuild(int& calls, vector<int>& cur, vector<int>& rem) {
	++calls;

	int k = 0;
	int m = rem.size();
	if (m == 0) return true;
	for (int i = 0; i+k < m; ++i) {
		swap(rem[i], rem[i+k]);
		if (!cur.empty() && !is_prime[cur.back() + rem[i]]) {
			++k;
			--i;
		}
	}

	/*
	cerr << "recBuild( ";
	for (auto v : cur) cerr << v << ' '; cerr << ";; ";
	for (auto v : rem) cerr << v << ' '; cerr << ")" << endl;
	*/

	for (int i = 0; i < m-k && calls < H; ++i) {
		int v = rem[i];
		swap(rem[i], rem.back());
		rem.pop_back();
		cur.push_back(v);

		bool succ = recBuild(calls, cur, rem);
		if (succ) return true;

		cur.pop_back();
		rem.push_back(v);
		swap(rem[i], rem.back());
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;

	for (int i = 2; i <= 2*n; ++i) is_prime[i] = 1;
	for (int i = 2; i <= 2*n; ++i) {
		if (is_prime[i]) {
			for (int j = 2*i; j < 2*n; j += i) is_prime[j] = 0;
		}
	}
	vector<int> cur(n), res;
	for (int i = 0; i < n; ++i) cur[i] = i+1;

	while(true) {
		int calls = 0;
		bool succ = recBuild(calls, res, cur);
		if (succ) break;
	}
	for (int& v : res) cout << v << ' '; 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 4 3 2` view save

Test 4

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`5` view save

correct output
`3 4 1 2 5` view save

user output
`1 5 2 3 4` 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
`1 6 5 2 3 4` 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
`1 2 5 6 7 4 3` 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
`1 2 3 8 5 6 7 4` 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
`1 2 9 4 7 6 5 8 3` 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
`1 10 9 2 5 6 7 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
`1 2 17 12 11 6 13 4 7 10 19 18...` view save

Test 11

Group: 2, 3

Verdict: WRONG ANSWER

input
`56` view save

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

user output
`1 2 3 4 15 14 47 50 51 28 13 4...` Truncated

Test 12

Group: 2, 3

Verdict: WRONG ANSWER

input
`70` view save

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

user output
`1 70 69 40 27 62 65 14 9 44 63...` 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
`1 2 21 20 69 62 17 66 7 46 15 ...` Truncated

Test 14

Group: 2, 3

Verdict: WRONG ANSWER

input
`90` view save

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

user output
`1 2 27 86 81 8 21 76 63 46 25 ...` Truncated

Test 15

Group: 2, 3

Verdict: WRONG ANSWER

input
`100` view save

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

user output
`1 100 99 82 97 66 85 24 89 60 ...` Truncated

Test 16

Group: 3

Verdict: WRONG ANSWER

input
`154` view save

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

user output
`1 2 11 128 149 8 93 56 135 98 ...` Truncated

Test 17

Group: 3

Verdict: WRONG ANSWER

input
`430` view save

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

user output
`1 430 429 148 81 268 133 180 4...` Truncated

Test 18

Group: 3

Verdict: WRONG ANSWER

input
`629` view save

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

user output
`1 2 125 264 445 42 589 168 13 ...` Truncated

Test 19

Group: 3

Verdict: WRONG ANSWER

input
`833` view save

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

user output
`1 2 147 340 393 526 91 256 205...` Truncated

Test 20

Group: 3

Verdict: WRONG ANSWER

input
`885` view save

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

user output
`1 2 155 116 795 806 215 824 19...` Truncated

Test 21

Group: 3

Verdict: WRONG ANSWER

input
`1000` view save

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

user output
`1 2 171 946 157 10 99 448 19 5...` 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 (mango_lassi)