Submission #316127

#	Time	Username	Problem	Language	Result	Execution time	Memory
316127		nikatamliani	Sorting (IOI15_sorting)	C++14	100 / 100	340 ms	20088 KiB

sorting

#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    vector < int > _Q(N), _P(N), _S(N), id(N);
    int l = 0, r = M - 1, ans = -1;
    while(r >= l) {
        auto SWAP = [&](int i, int j) {
            swap(id[_S[i]], id[_S[j]]);
            swap(_S[i], _S[j]);
        };
        for(int i = 0; i < N; ++i) _S[i] = S[i];
        int m = l + r >> 1;
        int swaps = -1;
        for(int i = 0; i < m; ++i) {
            swap(_S[X[i]], _S[Y[i]]);
        }
        for(int i = 0; i < N; ++i) {
            id[_S[i]] = i; 
        }
        for(int i = 0; i < N; ++i) {
            if(id[i] == i) continue; 
            _P[++swaps] = i;
            _Q[swaps] = _S[i];
            SWAP(id[i], i);
        }
        if(swaps + 1 <= m) {
            for(int i = 0; i < N; ++i) _S[i] = S[i];
            for(int i = 0; i < N; ++i) id[_S[i]] = i; 
            for(int i = 0; i < m; ++i) {
                SWAP(X[i], Y[i]);
                if(i <= swaps) {
                    P[i] = id[_P[i]];
                    Q[i] = id[_Q[i]];
                    SWAP(id[_P[i]], id[_Q[i]]);
                } else {
                    P[i] = Q[i] = 0;
                }
            }
            r = m - 1;
            ans = m;
        } else {
            l = m + 1;
        }
    }
    return ans;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:13:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |         int m = l + r >> 1;
      |                 ~~^~~

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26