CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Turnaus
Sender:
Submission time:2015-12-20 14:40:59 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.05 s1details
#20.06 s1details
#30.05 s1details
#40.05 s1details
#50.05 s1details
#60.05 s2details
#70.04 s2details
#80.05 s2details
#90.06 s2details
#10ACCEPTED0.05 s2details
#110.05 s3details
#120.05 s3details
#130.06 s3details
#140.05 s3details
#150.05 s3details
#160.14 s3details
#170.14 s3details
#180.17 s3details
#190.14 s3details
#20ACCEPTED0.11 s3details

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>

typedef long long LL;
using namespace std;

LL next_pow_2(LL n){
    LL x = 1;
    while(x < n) x *= 2;
    return x;
}

int main(){
    LL n; cin >> n;
    multiset<pair<LL,LL> > dudes; // needed games, dude id
    for(int i = 0; i < n; i++){
        LL x; cin >> x;
        dudes.insert({x,i+1});
    }
    
    vector<pair<LL,LL> > games;
    
    while(true){
        while(!dudes.empty() && dudes.rbegin()->first == 0)
            dudes.erase(--dudes.end());
        if(dudes.empty()) break;
        LL needed_1 = dudes.rbegin()->first;
        LL id_1 = dudes.rbegin()->second;
        dudes.erase(--dudes.end());

        while(!dudes.empty() && dudes.rbegin()->first == 0)
            dudes.erase(--dudes.end());
        if(dudes.empty()){
            cout << "QAQ" << endl;
            return 0;
        }
        LL needed_2 = dudes.rbegin()->first;
        LL id_2 = dudes.rbegin()->second;
        dudes.erase(--dudes.end());

        games.push_back({id_1,id_2});

        if(needed_1 > 0)
            dudes.insert({needed_1-1,id_1});
        if(needed_2 > 0)
            dudes.insert({needed_2-1,id_2});
    }
    
    cout << games.size() << "\n";
    for(auto p : games) cout << p.first << " " << p.second << "\n";
    
}


Test details

Test 1

Group: 1

Verdict:

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 8
9 8
9 5
4 10
...

Test 2

Group: 1

Verdict:

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 6
10 4
1 10
6 5
...

Test 3

Group: 1

Verdict:

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 2
10 2
10 5
10 3
...

Test 4

Group: 1

Verdict:

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 7
10 7
10 4
10 9
...

Test 5

Group: 1

Verdict:

input
10
5 8 5 5 8 4 0 1 4 0

correct output
QAQ

user output
20
5 2
5 2
5 2
5 4
...

Test 6

Group: 2

Verdict:

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 89
96 89
100 96
89 100
...

Test 7

Group: 2

Verdict:

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 100
97 100
97 100
97 77
...

Test 8

Group: 2

Verdict:

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 97
90 97
90 97
90 97
...

Test 9

Group: 2

Verdict:

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 87
99 88
99 87
99 88
...

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:

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 87
96 87
96 87
96 87
...

Test 12

Group: 3

Verdict:

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 96
100 96
100 96
100 96
...

Test 13

Group: 3

Verdict:

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 85
92 85
92 85
92 85
...

Test 14

Group: 3

Verdict:

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 84
87 84
87 89
87 84
...

Test 15

Group: 3

Verdict:

input
100
40 95 88 91 27 5 93 69 46 50 7...

correct output
QAQ

user output
2450
57 46
57 96
57 46
96 57
...

Test 16

Group: 3

Verdict:

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 10
15 14
15 10
15 6
...

Test 17

Group: 3

Verdict:

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 66
6 66
6 37
16 6
...

Test 18

Group: 3

Verdict:

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 12
16 12
6 4
30 16
...

Test 19

Group: 3

Verdict:

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 27
9 6
27 9
6 207
...

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