— Dark mode

Aalto Competitive Programming 2026 - wk4 - Wed

Pair sort

  • Start: 2026-09-23 16:20:00
  • End: 2026-09-23 17:50:00
Submission details
Task:Pair sort
Sender:aalto26dw_001
Submission time:2026-09-23 17:21:50 +0300
Language:C++ (C++23)
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.01 sdetails
#110.03 sdetails
#120.03 sdetails
#130.43 sdetails
#140.43 sdetails

Code

#include "iostream"
#include "algorithm"
#include "vector"
#include "map"
#include "cmath"


int main() {
    int n;
    std::cin >> n;
    std::vector<int> array(2 * n);
    std::map<int, std::vector<int>> pairs;

    for (int i = 0; i < 2 * n; i++) {
        std::cin >> array[i];
        pairs[array[i]].push_back(i + 1);
        if (pairs[array[i]].size() == 2) {
            if (std::abs(pairs[array[i]][0] - pairs[array[i]][1]) <= 1) pairs.erase(array[i]);
        }
    }
    int k = 0;
    std::vector<std::vector<int>> swaps;
    int curr = 1;
    while (!pairs.empty() && curr < n) {
        if (pairs.find(curr) == pairs.end()) {
            curr++;
            continue;
        }
        int next = curr + 1;
        int toSwap1 = 0, toSwap2 = 0;
        while (next <= n) {
            if (pairs.find(next) == pairs.end()) {
                next++;
            } else if (std::abs(pairs[next][0] - pairs[curr][0]) == 1) {
                toSwap1 = 0;
                break;
            } else if (std::abs(pairs[next][1] - pairs[curr][0]) == 1) {
                toSwap1 = 1;
                break;
            } else if (std::abs(pairs[next][0] - pairs[curr][1]) == 1) {
                toSwap2  = 1;
                break;
            } else if (std::abs(pairs[next][1] - pairs[curr][1]) == 1) {
                toSwap1 = 1;
                toSwap2 = 1;
                break;
            }
            else next++;
        }
        std::vector<int> newSwap = {pairs[curr][toSwap2], pairs[next][toSwap1]};
        swaps.push_back(newSwap);
        std::swap(pairs[curr][toSwap1], pairs[curr][toSwap2]);
        k++;
        pairs.erase(curr);
        curr++;
    }

    std::cout << k << std::endl;
    for (auto& swap : swaps) {
        std::cout << swap[0] << ' ' << swap[1] << std::endl;
    }
}

Test details

Test 1

Verdict:

input
5
3 2 4 5 1 3 2 1 4 5 
view save

correct output
3
2 6
4 9
6 8
view save

user output
(empty)

Test 2

Verdict:

input
5
3 2 4 5 1 3 2 1 4 5 
view save

correct output
3
2 6
4 9
6 8
view save

user output
(empty)

Test 3

Verdict:

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

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

user output
6
15 14
11 12
17 16
9 10
...
view save

Test 4

Verdict:

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

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

user output
6
15 14
11 12
17 16
9 10
...
view save

Test 5

Verdict:

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

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

user output
(empty)

Test 6

Verdict:

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

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

user output
(empty)

Test 7

Verdict:

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

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

user output
(empty)

Test 8

Verdict:

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

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

user output
(empty)

Test 9

Verdict:

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

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

user output
(empty)

Test 10

Verdict:

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

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

user output
(empty)

Test 11

Verdict:

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

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

user output
(empty)

Test 12

Verdict:

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

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

user output
(empty)

Test 13

Verdict:

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

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

user output
(empty)

Test 14

Verdict:

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

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

user output
(empty)

Tasks

A Pair sortB BathhouseC Sorting booksD ConurbationE Box Stack II

Submissions (aalto26dw_001)

2026-09-23 17:48:58 2026-09-23 17:47:51 2026-09-23 17:43:51 2026-09-23 17:24:00 2026-09-23 17:21:50