CSES - Aalto Competitive Programming 2024 - wk4 - Wed - Results
Submission details
Task:Pair sort
Sender:aalto2024d_006
Submission time:2024-09-25 17:42:49 +0300
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#10.00 sdetails
#20.00 sdetails
#30.00 sdetails
#40.01 sdetails
#50.00 sdetails
#60.00 sdetails
#70.00 sdetails
#80.00 sdetails
#90.01 sdetails
#100.01 sdetails
#110.01 sdetails
#120.01 sdetails
#130.02 sdetails
#140.02 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0; i < swaps.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~

Code

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> numbers(2* n);
    for (int i = 0; i < 2 * n; ++i) {
        cin >> numbers[i];
    }

    unordered_map<int, vector<int>> pos_map;
    for (int i = 0; i < 2 *n; ++i) {
        pos_map[numbers[i]].push_back(i);
    }

    vector<pair<int, int>> swaps;
    for (int i = 0; i < 2 * n; i += 2) {
        int num = numbers[i];
        if (numbers[i +1] != num) {
            int pos = pos_map[num][1];
            swaps.push_back(make_pair(i + 1, pos));
            swap(numbers[i + 1], numbers[pos]);
            pos_map[numbers[pos]].pop_back();
            pos_map[num][1] = i+ 1;
        } 
        else {
            pos_map[num].erase(pos_map[num].begin());
        }
    }

    cout << swaps.size() << endl;
    for (int i = 0; i < swaps.size(); ++i) {
        cout << swaps[i].first + 1 << " " << swaps[i].second + 1 << endl;
    }
}

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
(empty)

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
(empty)

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
2 17
4 3
6 5
8 7
...

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
2 17
4 3
6 5
8 7
...

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
2 87
4 78
6 71
8 55
...
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
50
2 87
4 78
6 71
8 55
...
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
2 77
4 108
6 141
8 55
...
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
2 77
4 108
6 141
8 55
...
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
500
2 758
4 820
6 125
8 243
...
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
500
2 758
4 820
6 125
8 243
...
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
2 256
4 1534
6 816
8 1057
...
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
2 256
4 1534
6 816
8 1057
...
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
2 1548
4 9062
6 6397
8 8296
...
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
2 1548
4 9062
6 6397
8 8296
...
Truncated