Submission #384406

#	Time	Username	Problem	Language	Result	Execution time	Memory
384406		doowey	Sorting (IOI15_sorting)	C++14	100 / 100	539 ms	34716 KiB

sorting

#include <bits/stdc++.h>
#include "sorting.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 10;
int seq[N];
int n, m;
vector<pii> sw;
int who[N];

int nex[N];
int cac[N];

int cur[N];
int ind[N];

vector<pii> soln;

bool can(int k){
    soln.clear();
    for(int i = 0 ; i < n; i ++ ){
        who[i] = i;
        cur[i] = seq[i];
        ind[cur[i]] = i;
    }
    for(int i = 0 ; i < k ; i ++ ){
        swap(who[sw[i].fi], who[sw[i].se]);
    }
    for(int i = 0 ; i < n; i ++ ){
        nex[who[i]] = i;
    }
    for(int i = 0 ; i < n; i ++ ){
        cac[nex[i]] = i;
    }
    int cnt = 0;
    int pi, qi;
    for(int i = 0 ; i < k; i ++ ){
        swap(nex[sw[i].fi], nex[sw[i].se]);
        cac[nex[sw[i].fi]] = sw[i].fi;
        cac[nex[sw[i].se]] = sw[i].se;
        swap(cur[sw[i].fi], cur[sw[i].se]);
        ind[cur[sw[i].fi]] = sw[i].fi;
        ind[cur[sw[i].se]] = sw[i].se;
        while(cnt < n){
            if(ind[cnt] == cac[cnt]) cnt ++ ;
            else{
                break;
            }
        }
        if(cnt == n){
            soln.push_back(mp(0, 0));
        }
        else{
            pi = ind[cnt];
            qi = cac[cnt];
            soln.push_back(mp(pi, qi));
            swap(cur[pi], cur[qi]);
            ind[cur[pi]] = pi;
            ind[cur[qi]] = qi;
        }
    }
    while(cnt < n){
        if(ind[cnt] == cac[cnt]) cnt ++ ;
        else{
            break;
        }
    }
    if(cnt == n)
        return true;
    else
        return false;
}

int findSwapPairs(int _N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    P[0] = 0;
	Q[0] = 0;
	n = _N;
	m = M;
    for(int i = 0 ; i < n; i ++ ){
        seq[i] = S[i];
    }
    for(int i = 0 ; i < m ; i ++ ){
        sw.push_back(mp(X[i], Y[i]));
    }
    int l = 0, r = m;
    int mid;
    while(l < r){
        mid = (l + r) / 2;
        if(can(mid))
            r = mid;
        else
            l = mid + 1;
    }
    can(l);
    for(int i = 0 ; i < l ; i ++ ){
        P[i] = soln[i].fi;
        Q[i] = soln[i].se;
    }
	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