Task: | Turnaus |
Sender: | |
Submission time: | 2015-12-20 14:11:06 +0200 |
Language: | C++ |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 19 |
#2 | ACCEPTED | 42 |
#3 | ACCEPTED | 39 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.06 s | 1 | details |
#2 | ACCEPTED | 0.06 s | 1 | details |
#3 | ACCEPTED | 0.06 s | 1 | details |
#4 | ACCEPTED | 0.05 s | 1 | details |
#5 | ACCEPTED | 0.06 s | 1 | details |
#6 | ACCEPTED | 0.06 s | 2 | details |
#7 | ACCEPTED | 0.07 s | 2 | details |
#8 | ACCEPTED | 0.06 s | 2 | details |
#9 | ACCEPTED | 0.06 s | 2 | details |
#10 | ACCEPTED | 0.06 s | 2 | details |
#11 | ACCEPTED | 0.06 s | 3 | details |
#12 | ACCEPTED | 0.06 s | 3 | details |
#13 | ACCEPTED | 0.05 s | 3 | details |
#14 | ACCEPTED | 0.05 s | 3 | details |
#15 | ACCEPTED | 0.05 s | 3 | details |
#16 | ACCEPTED | 0.07 s | 3 | details |
#17 | ACCEPTED | 0.10 s | 3 | details |
#18 | ACCEPTED | 0.09 s | 3 | details |
#19 | ACCEPTED | 0.07 s | 3 | details |
#20 | ACCEPTED | 0.07 s | 3 | details |
Code
#include <iostream>#include <vector>#include <cassert>using namespace std;const int MN=1<<20;int xs[MN];vector<int> ys[MN];typedef pair<int,int> P;vector<P> res;int main() {int n;cin>>n;int sum=0;for(int i=0; i<n; ++i) {int x;cin>>x;if (x>=n) {cout<<"QAQ\n";return 0;}xs[i]=x;ys[x].push_back(i+1);sum+=x;}if (sum%2) {cout<<"QAQ\n";return 0;}for(int x=n; x>0; ) {if (ys[x].empty()) {x--;continue;}int a=ys[x].back();ys[x].pop_back();int z=x;int k=x;while(z > (int)ys[k].size() && k>0) {z -= ys[k].size();--k;}if (k==0) {cout<<"QAQ\n";return 0;}for(int i=k; i<=x; ++i) {int low=i==k ? ys[k].size()-z : 0;while((int)ys[i].size() > low) {int b = ys[i].back();res.push_back(P(a,b));ys[i].pop_back();ys[i-1].push_back(b);}}}assert((int)res.size() == sum/2);cout<<res.size()<<'\n';for(P p:res) {cout<<p.first<<' '<<p.second<<'\n';}}
Test details
Test 1
Group: 1
Verdict: ACCEPTED
input |
---|
10 5 4 2 6 6 3 4 7 8 5 |
correct output |
---|
25 9 8 9 5 9 4 9 10 ... |
user output |
---|
25 9 6 9 7 9 2 9 10 ... |
Test 2
Group: 1
Verdict: ACCEPTED
input |
---|
10 6 4 4 6 5 6 1 2 1 7 |
correct output |
---|
21 10 6 10 4 10 1 10 5 ... |
user output |
---|
21 10 8 10 3 10 2 10 5 ... |
Test 3
Group: 1
Verdict: ACCEPTED
input |
---|
10 3 5 3 2 3 1 1 1 1 6 |
correct output |
---|
13 10 2 10 5 10 3 10 1 ... |
user output |
---|
13 10 9 10 4 10 5 10 3 ... |
Test 4
Group: 1
Verdict: ACCEPTED
input |
---|
10 4 4 4 6 3 5 7 1 5 9 |
correct output |
---|
24 10 7 10 4 10 9 10 6 ... |
user output |
---|
24 10 8 10 5 10 3 10 2 ... |
Test 5
Group: 1
Verdict: ACCEPTED
input |
---|
10 5 8 5 5 8 4 0 1 4 0 |
correct output |
---|
QAQ |
user output |
---|
QAQ |
Test 6
Group: 2
Verdict: ACCEPTED
input |
---|
100 57 62 69 61 64 62 56 58 61 58 ... |
correct output |
---|
2850 96 89 96 100 96 91 96 68 ... |
user output |
---|
2850 96 97 96 83 96 84 96 62 ... |
Test 7
Group: 2
Verdict: ACCEPTED
input |
---|
100 52 56 50 52 63 53 56 65 47 55 ... |
correct output |
---|
2813 97 100 97 77 97 75 97 89 ... |
user output |
---|
2813 97 95 97 79 97 94 97 52 ... |
Test 8
Group: 2
Verdict: ACCEPTED
input |
---|
100 52 58 46 54 55 51 48 49 53 45 ... |
correct output |
---|
2421 90 97 90 78 90 61 90 94 ... |
user output |
---|
2421 90 83 90 99 90 95 90 76 ... |
Test 9
Group: 2
Verdict: ACCEPTED
input |
---|
100 53 44 41 54 34 44 44 51 42 38 ... |
correct output |
---|
2145 99 87 99 88 99 93 99 82 ... |
user output |
---|
2145 99 77 99 67 99 70 99 81 ... |
Test 10
Group: 2
Verdict: ACCEPTED
input |
---|
100 51 2 34 17 16 53 56 37 11 94 4... |
correct output |
---|
QAQ |
user output |
---|
QAQ |
Test 11
Group: 3
Verdict: ACCEPTED
input |
---|
100 49 55 47 49 57 47 59 52 51 52 ... |
correct output |
---|
2674 96 87 96 80 96 89 96 74 ... |
user output |
---|
2674 96 95 96 77 96 92 96 59 ... |
Test 12
Group: 3
Verdict: ACCEPTED
input |
---|
100 44 49 47 50 46 45 46 43 45 53 ... |
correct output |
---|
2361 100 96 100 88 100 99 100 81 ... |
user output |
---|
2361 100 94 100 65 100 97 100 74 ... |
Test 13
Group: 3
Verdict: ACCEPTED
input |
---|
100 55 50 46 47 48 54 59 51 50 43 ... |
correct output |
---|
2318 92 85 92 71 92 53 92 56 ... |
user output |
---|
2318 92 95 92 59 92 42 92 52 ... |
Test 14
Group: 3
Verdict: ACCEPTED
input |
---|
100 45 51 47 56 47 51 47 55 57 41 ... |
correct output |
---|
2464 87 84 87 89 87 73 87 88 ... |
user output |
---|
2464 87 71 87 53 87 66 87 41 ... |
Test 15
Group: 3
Verdict: ACCEPTED
input |
---|
100 40 95 88 91 27 5 93 69 46 50 7... |
correct output |
---|
QAQ |
user output |
---|
QAQ |
Test 16
Group: 3
Verdict: ACCEPTED
input |
---|
100000 25 24 26 22 24 31 23 22 16 32 ... |
correct output |
---|
100000 15 10 15 14 15 6 15 12 ... |
user output |
---|
100000 15 614 15 274 15 184 15 172 ... |
Test 17
Group: 3
Verdict: ACCEPTED
input |
---|
100000 27 24 25 26 18 32 26 19 21 19 ... |
correct output |
---|
100000 6 66 6 37 6 16 6 62 ... |
user output |
---|
100000 6 230 6 211 6 186 6 105 ... |
Test 18
Group: 3
Verdict: ACCEPTED
input |
---|
100000 22 28 23 31 26 31 25 27 22 29 ... |
correct output |
---|
100000 16 12 16 6 16 4 16 30 ... |
user output |
---|
100000 16 226 16 46 16 44 16 449 ... |
Test 19
Group: 3
Verdict: ACCEPTED
input |
---|
100000 19 26 25 24 25 29 20 23 30 22 ... |
correct output |
---|
100000 9 27 9 6 9 207 9 156 ... |
user output |
---|
100000 9 2402 9 1240 9 819 9 351 ... |
Test 20
Group: 3
Verdict: ACCEPTED
input |
---|
100000 1 2 3 2 1 4 2 0 5 3 3 3 4 4 3 ... |
correct output |
---|
QAQ |
user output |
---|
QAQ |