CSES - Putka Open 2020 – 1/5

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
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.01 s	3	details
#18	ACCEPTED	0.01 s	3	details
#19	ACCEPTED	0.01 s	3	details
#20	ACCEPTED	0.01 s	3	details
#21	ACCEPTED	0.01 s	3	details

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` 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: ACCEPTED

input
`5` view save

correct output
`3 4 1 2 5` view save

user output
`1 4 3 2 5` 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 4 3 2 5 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
`1 4 3 2 5 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
`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 3 8 5 6 7 4 9` 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 3 8 5 6 7 4 9 2` 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 10 3 8 5 6 7 4 9 2 11 18 13 ...` 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
`1 2 3 56 5 54 7 52 9 50 11 48 ...` 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
`1 70 3 68 5 66 7 64 9 62 11 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
`1 4 3 2 5 24 7 22 9 20 11 18 1...` 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
`1 10 3 8 5 6 7 4 9 2 11 90 13 ...` 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
`1 100 3 98 5 96 7 94 9 92 11 9...` 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
`1 4 3 2 5 24 7 22 9 20 11 18 1...` 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
`1 430 3 428 5 426 7 424 9 422 ...` 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
`1 4 3 2 5 12 7 10 9 8 11 6 13 ...` 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
`1 4 3 2 5 24 7 22 9 20 11 18 1...` 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
`1 2 3 134 5 132 7 130 9 128 11...` 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
`1 10 3 8 5 6 7 4 9 2 11 18 13 ...` 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 (tsiki2)