Task: | Maalarit |
Sender: | ollpu |
Submission time: | 2016-10-06 20:35:29 +0300 |
Language: | C++ |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | ACCEPTED | 25 |
#3 | ACCEPTED | 31 |
#4 | ACCEPTED | 32 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.05 s | 1 | details |
#2 | ACCEPTED | 0.06 s | 1 | details |
#3 | ACCEPTED | 0.06 s | 1 | details |
#4 | ACCEPTED | 0.06 s | 1 | details |
#5 | ACCEPTED | 0.05 s | 1 | details |
#6 | ACCEPTED | 0.06 s | 1 | details |
#7 | ACCEPTED | 0.05 s | 2 | details |
#8 | ACCEPTED | 0.06 s | 2 | details |
#9 | ACCEPTED | 0.05 s | 2 | details |
#10 | ACCEPTED | 0.06 s | 2 | details |
#11 | ACCEPTED | 0.05 s | 2 | details |
#12 | ACCEPTED | 0.06 s | 2 | details |
#13 | ACCEPTED | 0.06 s | 3 | details |
#14 | ACCEPTED | 0.06 s | 3 | details |
#15 | ACCEPTED | 0.06 s | 3 | details |
#16 | ACCEPTED | 0.05 s | 3 | details |
#17 | ACCEPTED | 0.07 s | 3 | details |
#18 | ACCEPTED | 0.05 s | 3 | details |
#19 | ACCEPTED | 0.08 s | 4 | details |
#20 | ACCEPTED | 0.08 s | 4 | details |
#21 | ACCEPTED | 0.08 s | 4 | details |
#22 | ACCEPTED | 0.07 s | 4 | details |
#23 | ACCEPTED | 0.08 s | 4 | details |
#24 | ACCEPTED | 0.05 s | 4 | details |
Code
// Ole varovainen.// Et luultavasti halua nähdä mitä alla on.#include <iostream>#include <algorithm>#include <set>using namespace std;#define F first#define S secondconst int N = 1<<17;pair<int,int> mint[N<<1];int p3t[N<<1];bool chosen[N];void build_mint() {for (int i = N-1; i > 0; --i) {if (mint[i*2].F < mint[i*2+1].F || mint[i*2+1].F == 0) {mint[i] = mint[i*2];} else {mint[i] = mint[i*2+1];}}}int mint_find(int a, int b) {a += N; b += N;int minv = mint[a].F, mini = mint[a].S;while (a <= b) {if (a&1 && mint[a++].F < minv) {minv = mint[a-1].F;mini = mint[a-1].S;}if (!(b&1) && mint[b--].F < minv) {minv = mint[b+1].F;mini = mint[b+1].S;}a >>= 1; b >>= 1;}return mini;}void p3t_add(int i) {i += N;while (i) {p3t[i]++;i >>= 1;}}void p3t_decr(int i) {i += N;while (i) {p3t[i]--;i >>= 1;}}int p3t_sum(int i) {i += N;int a = N;int sum = 0;while (a <= i) {if (a&1) sum += p3t[a++];if (!(i&1)) sum += p3t[i--];a >>= 1; i >>= 1;}return sum;}void ole() {while (true) cout << "asd";}int main() {ios_base::sync_with_stdio(0);cin.tie(0);int n;cin >> n;int t[n];pair<int, int> s[n];for (int i = 0; i < n; ++i) {cin >> t[i];s[i] = {t[i], i};mint[N+i] = {t[i], i};}build_mint();sort(s, s+n, greater<pair<int,int>>());long resultA = 0, resultB = 0, result;for (int i = 0; i < n; ++i) {if (i%2) resultA = max(resultA, (long)t[i]);else resultB = max(resultB, (long)t[i]);}result = resultA + resultB;bool m2improves = 0;int p1_v = s[0].F, p2_v = 0, p3_v = 0;set<int> sp_locs;int sp_n_p3[n];int is_p3[n];int msp_loc = s[0].S;sp_locs.insert(msp_loc);sp_n_p3[msp_loc] = -1;for (int si = 1; si < n; ++si) {int i = s[si].S, next_v = s[si+1].F;if (p3t[i+N] || chosen[i+1] || (i > 0 && chosen[i-1])) break;// clog << i << ": " << endl;set<int>::iterator it = sp_locs.upper_bound(i);if ((i+p3t_sum(i))%2 != (msp_loc+p3t_sum(msp_loc))%2) {// clog << "different, ";if (it == sp_locs.end()) {// - - ^ * - ^ - - X - -// *it--;int psp_loc = *it;if (sp_n_p3[psp_loc] != -1) abort();int p3_loc = mint_find(psp_loc+1, i-1);p3_v = max(p3_v, t[p3_loc]);p3t_add(p3_loc);sp_n_p3[psp_loc] = p3_loc;sp_n_p3[i] = -1;// clog << "new last";} else if (it == sp_locs.begin()) {// - - X - - ^ - * ^ - -// *int nsp_loc = *it;int p3_loc = mint_find(i+1, nsp_loc-1);p3_v = max(p3_v, t[p3_loc]);p3t_add(p3_loc);sp_n_p3[i] = p3_loc;// clog << "new first";} else {set<int>::iterator bit = it;bit--;int psp_loc = *bit, nsp_loc = *it;int pp3_loc = mint_find(psp_loc+1, i-1),np3_loc = mint_find(i+1, nsp_loc-1);int op_n_p3 = sp_n_p3[psp_loc];if (op_n_p3 == -1) {// - - ^ - - X - - ^ - -// * *p3_v = max(max(t[pp3_loc], t[np3_loc]), p3_v);sp_n_p3[psp_loc] = pp3_loc;sp_n_p3[i] = np3_loc;p3t_add(pp3_loc); p3t_add(np3_loc);// clog << "last unset";} else if (op_n_p3 < i) {// - - ^ * X - - ^ - -// - *p3_v = max(p3_v, t[np3_loc]);p3t_decr(op_n_p3);p3t_add(np3_loc);sp_n_p3[psp_loc] = -1;sp_n_p3[i] = np3_loc;// clog << "last before";} else {// - - ^ - - X * ^ - -// * -p3_v = max(p3_v, t[pp3_loc]);p3t_decr(op_n_p3);p3t_add(pp3_loc);sp_n_p3[psp_loc] = pp3_loc;sp_n_p3[i] = -1;// clog << "last after";}}} else {if (it == sp_locs.begin()) {sp_n_p3[i] = -1;} else {it--;int psp_loc = *it;int op_n_p3 = sp_n_p3[psp_loc];if (op_n_p3 != -1) {if (op_n_p3 < i) {// - - ^ * - X - ^ - -sp_n_p3[i] = -1;} else if (op_n_p3 > i) {// - - ^ - X - * ^ - -sp_n_p3[psp_loc] = -1;sp_n_p3[i] = op_n_p3;}} else {// - - ^ - - - X - ^sp_n_p3[i] = -1;}}}sp_locs.insert(i);p2_v = next_v;// clog << endl;// for (int j = 0; j < n; ++j) {// clog << p3t[j+N] << " ";// }// clog << endl;for (int j = 0; j < n; ++j) {if (p3t[j+N] != 0 && p3t[j+N] != 1) ole();}if ((long) p1_v + p2_v + p3_v < result) {m2improves = 1;result = (long) p1_v + p2_v + p3_v;for (int j = 0; j < n; ++j) {is_p3[j] = p3t[j+N];}}chosen[i] = 1;}if (m2improves) {cout << result << (p3_v ? " 3\n" : " 2\n");int invs = 0;for (int i = 0; i < n; ++i) {if (is_p3[i]) {invs++;cout << "3 ";} else if ((i+invs)%2) {cout << "2 ";} else {cout << "1 ";}}} else {cout << resultA+resultB << " 2" << endl;for (int i = 0; i < n; ++i) {if (i%2) cout << "2 "; else cout << "1 ";}}}
Test details
Test 1
Group: 1
Verdict: ACCEPTED
input |
---|
10 22 54 3 91 69 90 40 29 83 71 |
correct output |
---|
174 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
174 2 1 2 1 2 1 2 1 2 1 2 |
Test 2
Group: 1
Verdict: ACCEPTED
input |
---|
10 49 3 96 38 90 18 92 74 83 1 |
correct output |
---|
170 3 1 2 1 2 1 2 1 2 1 2 |
user output |
---|
170 2 1 2 1 2 1 2 1 2 1 2 |
Test 3
Group: 1
Verdict: ACCEPTED
input |
---|
10 46 3 41 30 16 17 12 93 80 81 |
correct output |
---|
173 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
173 2 1 2 1 2 1 2 1 2 1 2 |
Test 4
Group: 1
Verdict: ACCEPTED
input |
---|
10 46 8 95 85 82 73 82 92 53 90 |
correct output |
---|
187 3 1 2 1 2 1 2 1 2 1 2 |
user output |
---|
187 2 1 2 1 2 1 2 1 2 1 2 |
Test 5
Group: 1
Verdict: ACCEPTED
input |
---|
10 41 18 61 59 40 96 5 2 74 38 |
correct output |
---|
159 3 2 1 2 1 2 1 2 3 1 2 |
user output |
---|
159 3 1 2 1 2 1 2 1 3 2 1 |
Test 6
Group: 1
Verdict: ACCEPTED
input |
---|
10 1 1 1 1 1 1 1 1 1 1 |
correct output |
---|
2 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
2 2 1 2 1 2 1 2 1 2 1 2 |
Test 7
Group: 2
Verdict: ACCEPTED
input |
---|
100 1 39 94 5 24 84 84 10 78 61 38... |
correct output |
---|
193 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
193 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 8
Group: 2
Verdict: ACCEPTED
input |
---|
100 31 73 18 88 49 28 66 5 32 48 9... |
correct output |
---|
199 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
199 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 9
Group: 2
Verdict: ACCEPTED
input |
---|
100 45 56 36 60 31 10 23 79 29 17 ... |
correct output |
---|
198 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
198 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 10
Group: 2
Verdict: ACCEPTED
input |
---|
100 1 77 70 62 21 68 40 54 90 62 1... |
correct output |
---|
194 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
194 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 11
Group: 2
Verdict: ACCEPTED
input |
---|
100 4 47 41 81 56 64 12 10 20 100 ... |
correct output |
---|
189 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
189 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 12
Group: 2
Verdict: ACCEPTED
input |
---|
10 1 1 1 1 1 1 1 1 1 1 |
correct output |
---|
2 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
2 2 1 2 1 2 1 2 1 2 1 2 |
Test 13
Group: 3
Verdict: ACCEPTED
input |
---|
100 256160448 813097800 167146270 ... |
correct output |
---|
1929869257 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
1929869257 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 14
Group: 3
Verdict: ACCEPTED
input |
---|
100 520002672 3542567 24668528 959... |
correct output |
---|
1946957555 3 1 2 3 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
1946957555 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 15
Group: 3
Verdict: ACCEPTED
input |
---|
100 483158423 780224665 844754665 ... |
correct output |
---|
1959373560 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
1959373560 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 16
Group: 3
Verdict: ACCEPTED
input |
---|
100 969647264 128558017 889036329 ... |
correct output |
---|
1997942264 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
1997942264 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 17
Group: 3
Verdict: ACCEPTED
input |
---|
100 745018527 400495893 635468795 ... |
correct output |
---|
1961391143 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
1961391143 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 18
Group: 3
Verdict: ACCEPTED
input |
---|
10 1 1 1 1 1 1 1 1 1 1 |
correct output |
---|
2 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
2 2 1 2 1 2 1 2 1 2 1 2 |
Test 19
Group: 4
Verdict: ACCEPTED
input |
---|
100000 197349274 775463806 263930657 ... |
correct output |
---|
1999942635 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
1999942635 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 20
Group: 4
Verdict: ACCEPTED
input |
---|
100000 102296405 34648120 320393597 9... |
correct output |
---|
1999930943 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
1999930943 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 21
Group: 4
Verdict: ACCEPTED
input |
---|
100000 781254921 418252056 502363453 ... |
correct output |
---|
1999987794 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
1999987794 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 22
Group: 4
Verdict: ACCEPTED
input |
---|
100000 849784881 230439009 455097426 ... |
correct output |
---|
1999979439 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
1999979439 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 23
Group: 4
Verdict: ACCEPTED
input |
---|
100000 851456132 13422224 537539701 4... |
correct output |
---|
1999948226 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
1999948226 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 24
Group: 4
Verdict: ACCEPTED
input |
---|
100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
2 3 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 ... |
user output |
---|
2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |