CSES - Aalto Competitive Programming 2024 - wk4 - Wed - Results
Submission details
Task:Pair sort
Sender:aalto2024d_005
Submission time:2024-09-25 16:44:07 +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.00 sdetails
#100.00 sdetails
#110.00 sdetails
#120.00 sdetails
#130.02 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> numbers;

    for (int i = 0; i < 2*n; i++) {
        int a;
        cin >> a;
        numbers.push_back(a);
    }

    int swaps = 0;
    vector<vector<int>> swap_list; 

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

        // cout << "i: " << i << "\n";
        int n = numbers[i];

        int pair = numbers[i-1];

        // cout << n << " : " << pair << "\n";

        if (n != pair) {
            // look for pair number
            for (int j = i+1; j < 2*n; j++) {
                
                if (pair == numbers[j]) {
                    int temp = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = temp;

                    // cout << "swapped " << n-1 << " and " << j << "\n";
                    vector<int> swaps = {i+1, j+1};
                    swap_list.push_back(swaps);
                }
            }
            swaps++;
        }
        i++;
    }

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

    dbg(numbers);
    
    

    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
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
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
10

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
10

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
50
10 27
22 79
32 74
46 51

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
50
10 27
22 79
32 74
46 51

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
6 141
8 55
10 52
12 36
...
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
6 141
8 55
10 52
12 36
...
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
6 125
8 243
10 52
16 760
...
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
6 125
8 243
10 52
16 760
...
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
1000
2 256
4 1534
8 1057
14 657
...
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
1000
2 256
4 1534
8 1057
14 657
...
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
16 2907
18 7700
20 7764
22 1021
...
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
16 2907
18 7700
20 7764
22 1021
...
Truncated