Task: | Vaihdot |
Sender: | Sisuaski |
Submission time: | 2020-09-06 04:58:35 +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.02 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.02 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.02 s | 2, 3 | details |
#10 | ACCEPTED | 0.02 s | 2, 3 | details |
#11 | ACCEPTED | 0.02 s | 2, 3 | details |
#12 | ACCEPTED | 0.02 s | 2, 3 | details |
#13 | ACCEPTED | 0.02 s | 2, 3 | details |
#14 | ACCEPTED | 0.02 s | 2, 3 | details |
#15 | ACCEPTED | 0.02 s | 2, 3 | details |
#16 | ACCEPTED | 0.02 s | 2, 3 | details |
#17 | ACCEPTED | 0.14 s | 3 | details |
#18 | ACCEPTED | 0.51 s | 3 | details |
#19 | ACCEPTED | 0.08 s | 3 | details |
#20 | ACCEPTED | 0.08 s | 3 | details |
#21 | ACCEPTED | 0.08 s | 3 | details |
#22 | ACCEPTED | 0.10 s | 3 | details |
#23 | ACCEPTED | 0.49 s | 3 | details |
#24 | ACCEPTED | 0.68 s | 3 | details |
Code
#include <iostream>#include <vector>#include <algorithm>using namespace std;typedef long long ll;typedef pair<int,int> P;const int MN = 2<<17;int ord[MN];int pos[MN];bool isOk(int i) {if (pos[i-1] < pos[i+1]) return pos[i]>pos[i-1] && pos[i]<pos[i+1];return pos[i]<pos[i+1] || pos[i]>pos[i-1];}vector<int> tree[2*MN];P best = {0,0};void add(int a, int b, int x) {for(a+=MN, b+=MN; a<=b; a/=2, b/=2) {if (a&1) tree[a++].push_back(x);if (~b&1) tree[b--].push_back(x);}}int count(int n, int f, int t) {int res=0;int n0 = n;for(n+=MN; n>=1; n/=2) {auto a = lower_bound(tree[n].begin(), tree[n].end(), f);auto b = upper_bound(tree[n].begin(), tree[n].end(), t);res += b-a;if (a != b) best = {n0, *a};}return res;}void doSwap(int a, int b) {swap(ord[a], ord[b]);swap(pos[ord[a]], pos[ord[b]]);}bool isGoodSwap(int i) {int fst = (pos[i-1] < pos[i]) + (pos[i] < pos[i+1]) + (pos[i+1] < pos[i+2]);swap(pos[i], pos[i+1]);int snd = (pos[i-1] < pos[i]) + (pos[i] < pos[i+1]) + (pos[i+1] < pos[i+2]);swap(pos[i], pos[i+1]);return snd > fst;}void addIdx(int i, int n, int offset=0) {if (pos[i-1] < pos[i+1]) {add(pos[i-1]+offset, pos[i+1]-offset, pos[i]);} else {add(1, pos[i+1]-offset, pos[i]);add(pos[i-1]+offset, n, pos[i]);}}int getCnt(int i, int n) {if (pos[i-1] < pos[i+1]) {int x = count(pos[i], pos[i-1]+1, pos[i+1]-1);return x;} else {int x = count(pos[i], 1, pos[i+1]-1);int y = count(pos[i], pos[i-1]+1, n);return x+y;}}int main() {int n;cin>>n;for(int i=1; i<=n; ++i) cin>>ord[i];for(int i=1; i<=n; ++i) pos[ord[i]] = i;pos[n+1] = n+1;for(int i=1; i<=n; ++i) if (!isOk(i)) addIdx(i, n);for(auto& t: tree) sort(t.begin(), t.end());ll cnt = 0;for(int i=1; i<=n; ++i) if (!isOk(i)) cnt += getCnt(i, n);cnt /= 2;if (cnt == 0) {for(int i=1; i<=n; ++i) {if (isOk(i)) continue;int x = count(pos[i], 1, n);cnt += x;}for(int i=1; i<n; ++i) {if (isGoodSwap(i)) --cnt;}for(int i=1; i<=n; ++i) if (isOk(i)) cnt += getCnt(i, n);}if (cnt == 0) {for(int i=1; i<=n; ++i) {if (isOk(i)) {int x = count(pos[i], 1, n);cnt += x;}}for(auto& t: tree) t.clear();for(int i=1; i<=n; ++i) if (isOk(i)) addIdx(i, n, 1);int bcnt = 0;for(int i=1; i<=n; ++i) if (!isOk(i)) bcnt++;cnt += bcnt * (bcnt-1) / 2;for(auto& t: tree) sort(t.begin(), t.end());int okc = 0;for(int i=1; i<=n; ++i) {if (isOk(i)) {okc += getCnt(i, n);okc--;} else {int x = count(pos[i], 1, n);cnt += x;}}cnt += okc / 2;for(int i=1; i<n; ++i) {if (isOk(i) && isOk(i+1) && isGoodSwap(i)) {++cnt;}}}if (cnt == 0) {cnt = n-1;best = {1,2};}doSwap(best.first, best.second);int res=0;for(int i=1; i<=n; ++i) {if (i==1 || pos[i]<pos[i-1]) res++;}cout<<res<<' '<<cnt<<'\n';}
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 |