Submission #90237

#	Time	Username	Problem	Language	Result	Execution time	Memory
90237		Retro3014	Sorting (IOI15_sorting)	C++17	100 / 100	246 ms	18168 KiB

sorting

#include "sorting.h"
#include <vector>

using namespace std;
#define MAX_N 200000

vector<int> x, y, arr, idx;
vector<int> v;
bool vst[MAX_N+1];
int n, m;
int R;

int dfs(int x){
    if(vst[x])  return 0;
    vst[x]=true;
    return dfs(v[x])+1;
}

bool chk(){
    int cnt=0;
    v.clear();
    for(int i=0; i<n; i++){
        v.push_back(arr[i]);
        vst[i]=false;
    }
    for(int i=0; i<R; i++){
        int tmp=v[x[i]];
        v[x[i]]=v[y[i]];
        v[y[i]]=tmp;
    }
    for(int i=0; i<n; i++){
        if(!vst[i] && v[i]!=i){
            vst[i]=true;
            cnt+=dfs(v[i]);
        }
    }
    return (cnt<=R);
}

void sw(int aa, int bb){
    int tmp=idx[v[aa]];
    idx[v[aa]]=idx[v[bb]];
    idx[v[bb]]=tmp;
    tmp=v[aa];
    v[aa]=v[bb];
    v[bb]=tmp;
}


int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n=N; m=M;
    for(int i=0; i<N; i++){
        arr.push_back(S[i]);
        idx.push_back(0);
    }
    for(int i=0; i<M; i++){
        x.push_back(X[i]);
        y.push_back(Y[i]);
    }
    int s=0, e=M-1;
    while(s<e){
        R=(s+e)/2;
        if(chk()){
            e=R;
        }else{
            s=R+1;
        }
    }
    R=(s+e)/2;
    v.clear();
    int cnt=0;
    for(int i=0; i<n; i++){
        v.push_back(arr[i]);
        vst[i]=false;
    }
    for(int i=0; i<R; i++){
        int tmp=v[x[i]];
        v[x[i]]=v[y[i]];
        v[y[i]]=tmp;
    }
    for(int i=0; i<n; i++){
        while(v[i]!=i){
            P[cnt]=v[i];
            Q[cnt]=v[v[i]];
            cnt++;
            int tmp=v[i];
            v[i]=v[v[i]];
            v[tmp]=tmp;
        }
    }
    v.clear();
    for(int i=0; i<n; i++){
        v.push_back(arr[i]);
        idx[v[i]]=i;
    }
    while(cnt<R){
        P[cnt]=1;
        Q[cnt]=1;
        cnt++;
    }
    for(int i=0; i<R; i++){
        sw(X[i], Y[i]);
        P[i]=idx[P[i]];
        Q[i]=idx[Q[i]];
        sw(P[i], Q[i]);
    }
	return R;
}

Compilation message (stderr)

sorting.cpp: In function 'int dfs(int)':
sorting.cpp:13:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 int dfs(int x){
              ^
sorting.cpp:7:13: note: shadowed declaration is here
 vector<int> x, y, arr, idx;
             ^

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