Submission #1220859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220859		Malix	Sorting (IOI15_sorting)	C++20	100 / 100	170 ms	11384 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) x.begin(),x.end()

int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    bool flag=1;
    REP(i,0,n)if(S[i]!=i)flag=0;
    if(flag)return 0;
    int l=1,r=n;
    while(l!=r){
        int m=(l+r)/2;
        vi arr(n);
        REP(i,0,n)arr[i]=i;
        vi a=arr,b=arr,c(n),d(n);
        REP(i,0,n)c[i]=S[i];
        REP(i,0,n)d[c[i]]=i;
        REP(i,0,m)swap(arr[X[i]],arr[Y[i]]);
        int pos=0;
        REP(i,0,m){
            swap(b[X[i]],b[Y[i]]);
            swap(a[b[X[i]]],a[b[Y[i]]]);
            swap(c[X[i]],c[Y[i]]);
            swap(d[c[X[i]]],d[c[Y[i]]]);
            while(pos<n&&d[pos]==a[arr[pos]])pos++;
            if(pos==n)break;
            int x=d[pos],y=a[arr[pos]];
            swap(c[x],c[y]);
            swap(d[c[x]],d[c[y]]);
            pos++;
            while(pos<n&&d[pos]==a[arr[pos]])pos++;
            if(pos==n)break;
        }
        if(pos==n)r=m;
        else l=m+1;
    }
    vi arr(n);
    REP(i,0,n)arr[i]=i;
    vi a=arr,b=arr,c(n),d(n);
    REP(i,0,n)c[i]=S[i];
    REP(i,0,n)d[c[i]]=i;
    REP(i,0,l)swap(arr[X[i]],arr[Y[i]]);
    int pos=0;
    REP(i,0,l){
        swap(b[X[i]],b[Y[i]]);
        swap(a[b[X[i]]],a[b[Y[i]]]);
        swap(c[X[i]],c[Y[i]]);
        swap(d[c[X[i]]],d[c[Y[i]]]);
        while(pos<n&&d[pos]==a[arr[pos]])pos++;
        if(pos==n){
            P[i]=0;
            Q[i]=0;
            break;
        }
        P[i]=a[arr[pos]];
        Q[i]=d[pos];
        swap(c[P[i]],c[Q[i]]);
        swap(d[c[P[i]]],d[c[Q[i]]]);
        pos++;
        while(pos<n&&d[pos]==a[arr[pos]])pos++;
        if(pos==n)break;
    }
    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