Submission #670089

#	Time	Username	Problem	Language	Result	Execution time	Memory
670089		Astrayt	Sorting (IOI15_sorting)	C++17	100 / 100	362 ms	19300 KiB

sorting

#include <bits/stdc++.h>
using namespace std;
#define starburst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//#define int long long
#define pii pair<int,int>
#define pb push_back

int findSwapPairs(int N, int *S, int M, int *X, int *Y, int *P, int *Q){
    int lb = 0, rb = M;
    while(lb != rb){
        int mid = (lb + rb) / 2;
        vector<int> cur(N), end(N), curid(N), endid(N);
        for(int i = 0; i < N; ++i) cur[i] = end[i] = S[i], curid[S[i]] = endid[S[i]] = i;
        for(int i = 0; i < mid; ++i){
            int x = X[i], y = Y[i];
            endid[end[x]] = y, endid[end[y]] = x;
            swap(end[x], end[y]);
        }
        int j = N - 1;
        for(int i = mid - 1; i >= 0; --i){
            while(j >= 0 && end[j] == j) j--;
            if(j < 0) break;
            int id = mid - i - 1;
            int x = X[id], y = Y[id];
            swap(curid[cur[x]], curid[cur[y]]);
            swap(cur[x], cur[y]);
            int a = end[j], b = j;
            swap(curid[a], curid[b]);
            swap(endid[a], endid[b]);
            swap(cur[curid[a]], cur[curid[b]]);
            swap(end[endid[a]], end[endid[b]]);
        }
        while(j >= 0 && end[j] == j) j--;
        if(j < 0) rb = mid;
        else lb = mid + 1;
    }
    vector<int> cur(N), end(N), curid(N), endid(N);
    for(int i = 0; i < N; ++i) cur[i] = end[i] = S[i], curid[S[i]] = endid[S[i]] = i;
    for(int i = 0; i < lb; ++i){
        int x = X[i], y = Y[i];
        endid[end[x]] = y, endid[end[y]] = x;
        swap(end[x], end[y]);
    }
    int j = N - 1;
    for(int i = lb - 1; i >= 0; --i){
        while(j >= 0 && end[j] == j) j--;
        if(j < 0) break;
        int id = lb - i - 1;
        int x = X[id], y = Y[id];
        swap(curid[cur[x]], curid[cur[y]]);
        swap(cur[x], cur[y]);
        int a = end[j], b = j;
        P[id] = curid[a], Q[id] = curid[b];
        if(P[id] > Q[id]) swap(P[id], Q[id]);
        swap(curid[a], curid[b]);
        swap(endid[a], endid[b]);
        swap(cur[curid[a]], cur[curid[b]]);
        swap(end[endid[a]], end[endid[b]]);
    }
    return lb;
}

/*void solve(){
    int n; cin >> n;
    int S[n];
    for(int i = 0; i < n; ++i) cin >> S[i];
    int m; cin >> m;
    int X[m], Y[m], P[m], Q[m];
    fill(P, P + m + 1, 0);
    fill(Q, Q + m + 1, 0);
    for(int i = 0; i < m; ++i) cin >> X[i] >> Y[i];
    int R = findSwapPairs(n, S, m, X, Y, P, Q);
    cout << R << '\n';
    for(int i = 0; i < R; ++i) cout << P[i] << ' ' << Q[i] << '\n';
}

signed main(){
    starburst
    int t = 1; //cin >> t;
    while(t--) solve();
}*/

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