Task: | Vaihdot |
Sender: | Hannes |
Submission time: | 2020-09-06 21:05:57 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 13 |
#2 | ACCEPTED | 23 |
#3 | ACCEPTED | 64 |
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 | 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 | 2, 3 | details |
#17 | ACCEPTED | 0.17 s | 3 | details |
#18 | ACCEPTED | 0.16 s | 3 | details |
#19 | ACCEPTED | 0.14 s | 3 | details |
#20 | ACCEPTED | 0.14 s | 3 | details |
#21 | ACCEPTED | 0.14 s | 3 | details |
#22 | ACCEPTED | 0.15 s | 3 | details |
#23 | ACCEPTED | 0.21 s | 3 | details |
#24 | ACCEPTED | 0.22 s | 3 | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:93:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int j=0;j<events[i].size();++j) { ~^~~~~~~~~~~~~~~~~
Code
#include <bits/stdc++.h>#define F first#define S secondusing namespace std;int n;const int SZ=(1<<19);int sp[3][SZ];void setv(int a, int T, int v) {a+=SZ/2;sp[T][a]=v;for (a/=2;a;a/=2) sp[T][a]=sp[T][2*a]+sp[T][2*a+1];}void settp(int a, int tp) {if (tp==0) {setv(a, 0, 1);setv(a, 1, 0);setv(a, 2, 0);}else if (tp==1) {setv(a, 0, 0);setv(a, 1, 1);setv(a, 2, 0);} else {setv(a, 0, 0);setv(a, 1, 0);setv(a, 2, 1);}}int gets(int a, int b, int tp) { a+=SZ/2;b+=SZ/2;int T=tp==0?0:(tp==1?1:2);int rv=0;while (a<b) {if (a&1) rv+=sp[T][a++];if (~b&1)rv+=sp[T][b--];a/=2;b/=2;}if (a==b) rv+=sp[T][a];return rv;}int a[202020];int k[202020];int pos[202020];// pair<index, event type>// event type=vector<pair<int, int> > events[202020];int best_swap=1000000;long long nof_best=0;void testbest(int a, int b, int delta) {int swaps;if (best_swap>=delta-1 && (swaps=gets(a, b, -1))) {if (best_swap==delta-1) nof_best+=swaps;else best_swap=delta-1, nof_best=swaps;} else if(best_swap>=delta+0 && (swaps=gets(a, b, 0))) {if (best_swap==delta+0) nof_best+=swaps;else best_swap=delta+0, nof_best=swaps;} else if (best_swap>=delta+1 && (swaps=gets(a, b, 1))) {if (best_swap==delta+1) nof_best+=swaps;else best_swap=delta+1, nof_best=swaps;}}int main() {cin >> n;for (int i=0;i<n;++i) cin >> a[i], pos[i+1]=-1;pos[n+1]=-1;int frags=0;for (int i=n-1;i>=0;--i) {int w=pos[a[i]+1];if (w!=-1) {k[i]=k[w]+1;k[w]=0;} else {k[i]=1;++frags;}pos[a[i]]=i;}// for (int i=0;i<n;++i) cout << k[i] << " ";cout << endl;// cout << frags << endl;for (int i=0;i<n;++i) {for (int j=0;j<events[i].size();++j) {int ix=events[i][j].F;int tp=events[i][j].S;settp(ix, tp);}int c=a[i];if (c==1) {if (pos[2]>i) {testbest(0, i-1, 0);events[i+1].push_back({i, 0});events[pos[2]].push_back({i, 1});} else {testbest(0, pos[2]-1, -1);testbest(pos[2], i-1, 0);events[i+1].push_back({i, 0});}} else if (c==n) {if (pos[n-1]>i) {testbest(0, i-1, 0);events[i+1].push_back({i, 0});events[pos[n-1]].push_back({i, -1});} else {testbest(0, pos[n-1]-1, 1);testbest(pos[n-1], i-1, 0);events[i+1].push_back({i, 0});}} else {if (pos[c-1]<i && i<pos[c+1]) { // 1 2 3testbest(0, pos[c-1]-1, 1);testbest(pos[c-1], i-1, 0);events[i+1].push_back({i, 0});events[pos[c+1]].push_back({i, 1});} else if (pos[c-1]<pos[c+1] && pos[c+1]<i) { // 1 3 2testbest(0, pos[c-1]-1, 0);testbest(pos[c-1], pos[c+1]-1, -1);testbest(pos[c+1], i-1, 0);events[i+1].push_back({i, 0});} else if (i<pos[c-1] && pos[c-1]<pos[c+1]) { // 2 1 3events[i+1].push_back({i, 0});events[pos[c-1]].push_back({i, -1});events[pos[c+1]].push_back({i, 0});} else if (i<pos[c+1] && pos[c+1]<pos[c-1]) { // 2 3 1events[i+1].push_back({i,0});events[pos[c+1]].push_back({i, 1});events[pos[c-1]].push_back({i, 0});} else if (pos[c+1]<i && i<pos[c-1]) { // 3 2 1testbest(0, pos[c+1]-1, -1);testbest(pos[c+1], i-1, 0);events[i+1].push_back({i, 0});events[pos[c-1]].push_back({i, -1});} else if (pos[c+1]<pos[c-1] && pos[c-1]<i) { // 3 1 2testbest(0, pos[c+1]-1, 0);testbest(pos[c+1], pos[c-1]-1, 1);testbest(pos[c-1], i-1, 0);events[i+1].push_back({i, 0});}}// cout << "~~" << c << ", " << pos[c-1] << " " << pos[c] << " " << pos[c+1] << endl;// cout << i << ": " << best_swap << ", " << nof_best << endl;}cout << best_swap+frags << " " << nof_best << endl;}
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
100 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
2 99 |
user output |
---|
2 99 |
Test 2
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
100 100 99 98 97 96 95 94 93 92 91... |
correct output |
---|
98 4851 |
user output |
---|
98 4851 |
Test 3
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
100 1 2 88 4 5 6 7 8 9 10 11 12 13... |
correct output |
---|
16 5 |
user output |
---|
16 5 |
Test 4
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
100 51 48 74 70 45 71 24 88 55 99 ... |
correct output |
---|
49 131 |
user output |
---|
49 131 |
Test 5
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
100 45 67 29 62 70 77 41 74 52 95 ... |
correct output |
---|
52 268 |
user output |
---|
52 268 |
Test 6
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
100 47 98 2 75 6 21 84 8 4 89 27 9... |
correct output |
---|
48 149 |
user output |
---|
48 149 |
Test 7
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
100 73 68 17 94 71 63 61 13 58 10 ... |
correct output |
---|
47 116 |
user output |
---|
47 116 |
Test 8
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
100 17 16 45 94 6 1 36 81 31 13 51... |
correct output |
---|
45 95 |
user output |
---|
45 95 |
Test 9
Group: 2, 3
Verdict: ACCEPTED
input |
---|
5000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
2 4999 |
user output |
---|
2 4999 |
Test 10
Group: 2, 3
Verdict: ACCEPTED
input |
---|
5000 5000 4999 4998 4997 4996 4995 ... |
correct output |
---|
4998 12492501 |
user output |
---|
4998 12492501 |
Test 11
Group: 2, 3
Verdict: ACCEPTED
input |
---|
5000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
19 10 |
user output |
---|
19 10 |
Test 12
Group: 2, 3
Verdict: ACCEPTED
input |
---|
5000 1 2 3 4 5 6 264 8 9 10 11 12 1... |
correct output |
---|
190 96 |
user output |
---|
190 96 |
Test 13
Group: 2, 3
Verdict: ACCEPTED
input |
---|
5000 1 2 3 4 5 6 7 8 9 2400 11 12 1... |
correct output |
---|
1378 27938 |
user output |
---|
1378 27938 |
Test 14
Group: 2, 3
Verdict: ACCEPTED
input |
---|
5000 4012 2 4820 4208 1868 1728 362... |
correct output |
---|
2511 436307 |
user output |
---|
2511 436307 |
Test 15
Group: 2, 3
Verdict: ACCEPTED
input |
---|
5000 3877 3972 1112 3669 1959 4640 ... |
correct output |
---|
2497 417065 |
user output |
---|
2497 417065 |
Test 16
Group: 2, 3
Verdict: ACCEPTED
input |
---|
5000 2774 998 4525 2884 487 1995 41... |
correct output |
---|
2518 426448 |
user output |
---|
2518 426448 |
Test 17
Group: 3
Verdict: ACCEPTED
input |
---|
200000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
2 199999 |
user output |
---|
2 199999 |
Test 18
Group: 3
Verdict: ACCEPTED
input |
---|
200000 200000 199999 199998 199997 19... |
correct output |
---|
199998 19999700001 |
user output |
---|
199998 19999700001 |
Test 19
Group: 3
Verdict: ACCEPTED
input |
---|
200000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
19 10 |
user output |
---|
19 10 |
Test 20
Group: 3
Verdict: ACCEPTED
input |
---|
200000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
199 100 |
user output |
---|
199 100 |
Test 21
Group: 3
Verdict: ACCEPTED
input |
---|
200000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
1979 1030 |
user output |
---|
1979 1030 |
Test 22
Group: 3
Verdict: ACCEPTED
input |
---|
200000 1 2 184153 4 5 6 7 8 164545 10... |
correct output |
---|
18081 477187 |
user output |
---|
18081 477187 |
Test 23
Group: 3
Verdict: ACCEPTED
input |
---|
200000 151013 68675 119105 58292 3335... |
correct output |
---|
86328 318722426 |
user output |
---|
86328 318722426 |
Test 24
Group: 3
Verdict: ACCEPTED
input |
---|
200000 11562 33356 106752 170825 2723... |
correct output |
---|
99873 663048119 |
user output |
---|
99873 663048119 |