Submission #1125261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125261		codexistent	Sorting (IOI15_sorting)	C++20	100 / 100	229 ms	13912 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define ll long long
#define FOR(i, a, b) for(ll i = a; i <= b; i++)

ll mxni[MAXN];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    ll l = 0, h = M;
    while(l < h){
        int m = (l + h) / 2;
        int s[N], slc[N];
        FOR(i, 0, N - 1) s[i] = i;
        for(int i = m - 1; i >= 0; i--){
            swap(s[X[i]], s[Y[i]]);
        }
        FOR(i, 0, N - 1) slc[s[i]] = i; 

        queue<int> q;

        int s2[N], lc[N];
        FOR(i, 0, N - 1) s2[i] = S[i], lc[S[i]] = i;
        FOR(i, 0, N - 1) if(slc[i] != lc[i]) q.push(i);

        FOR(i, 0, m - 1){
            swap(s[X[i]], s[Y[i]]), swap(slc[s[X[i]]], slc[s[Y[i]]]);
            swap(s2[X[i]], s2[Y[i]]), swap(lc[s2[X[i]]], lc[s2[Y[i]]]);

            while(q.size() && slc[q.front()] == lc[q.front()]){
                q.pop();
            }
            if(q.size()){
                int qi = q.front(); q.pop();
                P[i] = slc[qi];
                Q[i] = lc[qi];
                swap(s2[P[i]], s2[Q[i]]), swap(lc[s2[P[i]]], lc[s2[Q[i]]]);
            }else{
                P[i] = Q[i] = 0;
            }
        }
        
        FOR(i, 0, N - 1) if(s[i] != s2[i]) {
            l = m + 1;
            goto spot1;
        }
        h = m;
        spot1:;
    }

    int m = l;
    int s[N], slc[N];
    FOR(i, 0, N - 1) s[i] = i;
    for(int i = m - 1; i >= 0; i--){
        swap(s[X[i]], s[Y[i]]);
    }
    FOR(i, 0, N - 1) slc[s[i]] = i; 

    queue<int> q;

    int s2[N], lc[N];
    FOR(i, 0, N - 1) s2[i] = S[i], lc[S[i]] = i;
    FOR(i, 0, N - 1) if(slc[i] != lc[i]) q.push(i);

    FOR(i, 0, m - 1){
        swap(s[X[i]], s[Y[i]]), swap(slc[s[X[i]]], slc[s[Y[i]]]);
        swap(s2[X[i]], s2[Y[i]]), swap(lc[s2[X[i]]], lc[s2[Y[i]]]);

        while(q.size() && slc[q.front()] == lc[q.front()]){
            q.pop();
        }
        if(q.size()){
            int qi = q.front(); q.pop();
            P[i] = slc[qi];
            Q[i] = lc[qi];
            swap(s2[P[i]], s2[Q[i]]), swap(lc[s2[P[i]]], lc[s2[Q[i]]]);
        }else{
            P[i] = Q[i] = 0;
        }
    }

	return l;
}

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