CSES - Aalto Competitive Programming 2024 - wk4 - Wed - Results
Submission details
Task:Pair sort
Sender:aalto2024d_005
Submission time:2024-09-25 17:00:44 +0300
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#10.00 sdetails
#20.00 sdetails
#30.00 sdetails
#40.00 sdetails
#50.00 sdetails
#60.00 sdetails
#70.00 sdetails
#80.00 sdetails
#90.01 sdetails
#100.00 sdetails
#110.00 sdetails
#120.00 sdetails
#130.01 sdetails
#140.01 sdetails

Code

#include <bits/stdc++.h>

using namespace std;
#define int long long

// g++ <filename>.cpp -g -Wall -Wextra -DDEBUG -o <executable>

// copied from: https://codeforces.com/blog/entry/79024
// === Debug macro starts here ===

int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type operator<<(Ostream& os,  const Cont& v){
	os<<"[";
	for(auto& x:v){os<<x<<", ";}
	return os<<"]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p){
	return os<<"{"<<p.first<<", "<<p.second<<"}";
}

// === Debug macro ends here ===

signed main() {
    
    int n;
    cin >> n;

    vector<int> positions(2*n+1, -1); // saved indices
    vector<vector<int>> swap_list;

    int swaps = 0;

    for (int i = 1; i < 2*n; i++) {
        
        int number;
        cin >> number;

        if (positions[number] == -1) { // first encounter of number
            positions[number] = i;
        } else { // second encounter of number

            swaps++;
            vector<int> swap_numbers; 

            if (positions[number] % 2 != 0) { // odd index, swap after number
                swap_numbers = {positions[number] + 1, i};

                // update

            } else {
                swap_numbers = {positions[number] - 1 , i};                

                // update

            }

            swap_list.push_back(swap_numbers);
        }


    }

    cout << swaps << "\n";
    
    for (auto s : swap_list) {
        cout << s[0] << " " << s[1] << "\n";
    }
    
    

    return 0;
}

Test details

Test 1

Verdict:

input
5
3 2 4 5 1 3 2 1 4 5 

correct output
3
2 6
4 9
6 8

user output
4
2 6
1 7
6 8
4 9

Test 2

Verdict:

input
5
3 2 4 5 1 3 2 1 4 5 

correct output
3
2 6
4 9
6 8

user output
4
2 6
1 7
6 8
4 9

Test 3

Verdict:

input
10
3 6 6 8 8 9 9 1 4 5 2 4 10 2 1...

correct output
9
2 17
4 17
6 17
8 17
...

user output
9
1 3
3 5
5 7
10 12
...

Test 4

Verdict:

input
10
3 6 6 8 8 9 9 1 4 5 2 4 10 2 1...

correct output
9
2 17
4 17
6 17
8 17
...

user output
9
1 3
3 5
5 7
10 12
...

Test 5

Verdict:

input
50
47 26 6 35 13 18 9 19 14 50 34...

correct output
48
2 87
4 78
6 71
8 55
...

user output
49
15 23
10 27
27 29
18 30
...
Truncated

Test 6

Verdict:

input
50
47 26 6 35 13 18 9 19 14 50 34...

correct output
48
2 87
4 78
6 71
8 55
...

user output
49
15 23
10 27
27 29
18 30
...
Truncated

Test 7

Verdict:

input
100
56 26 6 35 60 72 9 55 83 51 58...

correct output
97
2 77
4 108
6 141
8 55
...

user output
99
7 13
5 21
15 23
18 30
...
Truncated

Test 8

Verdict:

input
100
56 26 6 35 60 72 9 55 83 51 58...

correct output
97
2 77
4 108
6 141
8 55
...

user output
99
7 13
5 21
15 23
18 30
...
Truncated

Test 9

Verdict:

input
500
56 146 351 35 281 235 354 449 ...

correct output
497
2 758
4 820
6 125
8 243
...

user output
499
10 52
34 77
44 81
29 93
...
Truncated

Test 10

Verdict:

input
500
56 146 351 35 281 235 354 449 ...

correct output
497
2 758
4 820
6 125
8 243
...

user output
499
10 52
34 77
44 81
29 93
...
Truncated

Test 11

Verdict:

input
1000
603 596 351 885 530 235 354 56...

correct output
993
2 256
4 1534
6 816
8 1057
...

user output
999
9 18
43 49
37 51
34 77
...
Truncated

Test 12

Verdict:

input
1000
603 596 351 885 530 235 354 56...

correct output
993
2 256
4 1534
6 816
8 1057
...

user output
999
9 18
43 49
37 51
34 77
...
Truncated

Test 13

Verdict:

input
5000
1594 596 1797 3776 1201 235 35...

correct output
4993
2 1548
4 9062
6 6397
8 8296
...

user output
4999
42 116
164 175
112 350
330 384
...
Truncated

Test 14

Verdict:

input
5000
1594 596 1797 3776 1201 235 35...

correct output
4993
2 1548
4 9062
6 6397
8 8296
...

user output
4999
42 116
164 175
112 350
330 384
...
Truncated