Submission #245287

#	Time	Username	Problem	Language	Result	Execution time	Memory
245287		ant101	정렬하기 (IOI15_sorting)	C++14	100 / 100	475 ms	21048 KiB

sorting

#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
#include <complex>
#include "sorting.h"
#include <algorithm>

using namespace std;

const int MAXN = 200005;

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
    int lo=0, hi=m;
    
    while(lo<hi){
        int mid=lo+(hi-lo)/2;
        vector<int> fp(n), fpidx(n), sc(s, s+n);
        for(int i=0;i<n;++i) fp[i]=i;
        
        for(int i=0;i<mid;++i){
            swap(fp[x[i]], fp[y[i]]);
        }
        for(int i=0;i<n;++i){
            fpidx[fp[i]]=i;
        }
        
        vector<int> perm(n), idx(n);
        for(int i=0;i<n;++i){
            perm[i]=i;
            idx[perm[i]]=i;
        }
        int j=0;
        for(int i=0;i<mid;++i){
            swap(sc[x[i]], sc[y[i]]);
            swap(perm[x[i]], perm[y[i]]);
            swap(idx[perm[x[i]]], idx[perm[y[i]]]);
            
            bool found=false;
            for(;j<n;j++){
                int jj=idx[j];
                if(fpidx[perm[jj]]!=sc[jj]){
                    found=true;
                    p[i]=jj;
                    q[i]=idx[fp[sc[jj]]];
                    swap(sc[p[i]], sc[q[i]]);
                    break;
                }
            }
            if(!found) p[i]=q[i]=0;
        }
        bool ok=true;
        for(int i=0;i<n;++i) if(sc[i]!=i) ok=false;
        if(ok){
            hi=mid;
        }else{
            lo=mid+1;
        }
        
    }
    vector<int> fp(n), fpidx(n), sc(s, s+n);
    for(int i=0;i<n;++i) fp[i]=i;
    
    for(int i=0;i<lo;++i){
        swap(fp[x[i]], fp[y[i]]);
    }
    for(int i=0;i<n;++i){
        fpidx[fp[i]]=i;
    }
    
    vector<int> perm(n), idx(n);
    for(int i=0;i<n;++i){
        perm[i]=i;
        idx[perm[i]]=i;
    }
    int j=0;
    for(int i=0;i<lo;++i){
        swap(sc[x[i]], sc[y[i]]);
        swap(perm[x[i]], perm[y[i]]);
        swap(idx[perm[x[i]]], idx[perm[y[i]]]);
        for(;j<n;j++){
            int jj=idx[j];
            if(fpidx[perm[jj]]!=sc[jj]){
                p[i]=jj;
                q[i]=idx[fp[sc[jj]]];
                swap(sc[p[i]], sc[q[i]]);
                break;
            }
        }
    }
    return lo;
}

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