Submission #99241

#	Time	Username	Problem	Language	Result	Execution time	Memory
99241		wilwxk	Sorting (IOI15_sorting)	C++17	Compilation error	0 ms	0 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];
set<int> s;
int n, m;

bool testa(int k) {
    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());
                // printf("case #1 %d\n", cara);
                r1[i]=vi[cara]; r2[i]=queroi[cara];
            }
        } else if(v[a]==quero[a]) {
            // printf("case #2\n");
            int cara=quero[b];
            r1[i]=vi[cara]; r2[i]=b;

        } else {
            // printf("case #3 %d - %d e %d\n", a, v[a], quero[a]);
            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;
    respf++; testa(respf);
    for(int i=1; i<=respf; i++) R1[i-1]=r1[i], R2[i-1]=r2[i];
    return respf;
}


int main() {
    // int n, v[100], m, x[100], y[100], r1[100], r2[100];
    // scanf("%d", &n);
    // for(int i=0; i<n; i++) scanf("%d", &v[i]);
    // scanf("%d", &m);
    // for(int i=0; i<m; i++) scanf("%d %d", &x[i], &y[i]);
    // int val=findSwapPairs(n, v, m, x, y, r1, r2);
    // printf(">>>> %d\n", val);
    // for(int i=0; i<val; i++) printf("%d %d\n", r1[i], r2[i]);

}

Compilation message (stderr)

/tmp/ccwueSJS.o: In function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'
/tmp/cczABAfH.o:sorting.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status