제출 #99243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99243		wilwxk	Sorting (IOI15_sorting)	C++17	74 / 100	580 ms	27360 KiB

sorting

#include <bits/stdc++.h>
using namespace std;

const int MAXN=2e5+3;
int ori[MAXN], quero[MAXN], queroi[MAXN];
int v[MAXN], vi[MAXN];
int x[MAXN], y[MAXN];
int r1[MAXN], r2[MAXN];
unordered_set<int> s;
int n, m;

bool testa(int k) {
    if(k<=0) return 0;
    for(int i=0; i<n; i++) {
        quero[i]=i; queroi[i]=i;
        v[i]=ori[i]; vi[v[i]]=i;
    }
    for(int i=k-1; i>=0; i--) {
        int a=x[i]; int b=y[i];
        swap(quero[a], quero[b]);
        queroi[quero[a]]=a; queroi[quero[b]]=b;
    }
    s.clear();
    for(int i=0; i<n; i++) if(v[i]!=quero[i]) s.insert(v[i]);
    // for(int i=0; i<n; i++) printf("%d ", quero[i]);

    for(int i=1; i<=k; i++) {
        int a=x[i]; int b=y[i];

        if(v[a]==quero[a]&&v[b]==quero[b]) {
            if(s.empty()) r1[i]=r2[i]=0;
            else {
                int cara=(*s.begin());
                r1[i]=vi[cara]; r2[i]=queroi[cara];
            }
        } else if(v[a]==quero[a]) {
            int cara=quero[b];
            r1[i]=vi[cara]; r2[i]=b;

        } else {
            int cara=quero[a];
            r1[i]=vi[cara]; r2[i]=a;
        }

        swap(v[r1[i]], v[r2[i]]);
        vi[v[r1[i]]]=r1[i]; vi[v[r2[i]]]=r2[i];
        if(v[r1[i]]==quero[r1[i]]) s.erase(v[r1[i]]);
        if(v[r2[i]]==quero[r2[i]]) s.erase(v[r2[i]]);
        // printf("%d %d\n", r1[i], r2[i]);
        // for(auto cur : s) printf("%d ", cur); printf("\n");

        swap(quero[a], quero[b]);
        queroi[quero[a]]=a; queroi[quero[b]]=b;

        if(i==k) break;
        swap(v[a], v[b]);
        vi[v[a]]=a; vi[v[b]]=b;
    }

    int ok=1;
    for(int i=0; i<n; i++) if(v[i]!=i) ok=0;
    return ok;
}

int findSwapPairs(int N, int V[], int M, int X[], int Y[], int R1[], int R2[]) {
    n=N; m=M;
    for(int i=0; i<n; i++) ori[i]=V[i];
    for(int i=0; i<m; i++) x[i]=X[i];
    for(int i=0; i<m; i++) y[i]=Y[i];

    int ok=1;
    for(int i=0; i<n; i++) if(ori[i]!=i) ok=0;
    if(ok) return 0;

    swap(ori[x[0]], ori[y[0]]);
    x[0]=0; y[0]=0;
    x[m]=0; y[m]=0;

    int respf=0;
    for(int i=m; i>0; i/=2) while(respf+i<=m&&testa(respf+i)==0) respf+=i;
    while(respf<=m&&!testa(respf)) respf++;
    if(!testa(respf)) assert(testa(m));
    for(int i=1; i<=respf; i++) R1[i-1]=r1[i], R2[i-1]=r2[i];
    return respf;
}

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