Submission #1212459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212459		XCAC197	Sorting (IOI15_sorting)	C++20	100 / 100	325 ms	29008 KiB

sorting

#include "sorting.h"
#include <algorithm>
#include <iostream>
#include <set>
#include <assert.h>
using namespace std;

int N;
int S [1000000];
int X [1000000];
int Y [1000000];

bool check(int M){
    int A_ [N];
    for(int i = 0; i < N; i++){
        A_[i] = i;
    }
    for(int i = M-1; i >= 0; i--){
        swap(A_[X[i]], A_[Y[i]]);
    }
    int A [N];
    for(int i = 0; i < N; i++){
        A[A_[i]] = S[i];
    }
    int numCyc = 0;
    bool vis [N];
    for(int i = 0; i < N; i++){
        vis[i] = false;
    }
    for(int i = 0; i < N; i++){
        if(!vis[i]){
            numCyc++;
            int cur = i;
            while(!vis[cur]){
                vis[cur] = true;
                cur = A[cur];
            }
        }
    }
  //  cerr << numCyc << endl;
    if((N - numCyc) <= M){
        return true;
    }else{
        return false;
    }
}

int findSwapPairs(int N_, int S_[], int M, int X_[], int Y_[], int P[], int Q[]) {
    N = N_;
    for(int i = 0; i < N; i++){
        S[i] = S_[i];
    }
    for(int i = 0; i < M; i++){
        X[i] = X_[i];
        Y[i] = Y_[i];
    }
    int A [N];
    int tmp [N];
    int Sinv [N];
    for(int i = 0; i < N; i++){
        A[i] = i;
        tmp[i] = S[i];
        Sinv[S[i]] = i;
    }
    int low = 0;
    int hig = M;
    while(low != hig){
        int mid = (low+hig)/2;
        if(check(mid)){
            hig = mid;
        }else{
            low = mid+1;
        }
    }
    M = low;
  //  cerr << M << endl;
    //go backwards
    for(int i = M-1; i >= 0; i--){
        swap(A[X[i]], A[Y[i]]);
    }
    set <int> mis;
    for(int i = 0; i < N; i++){
        if(A[i] != S[i]){
            mis.insert(i);
        }
    }
    for(int i = 0; i < M; i++){
        swap(A[X[i]], A[Y[i]]);
        swap(Sinv[S[X[i]]], Sinv[S[Y[i]]]);
        swap(S[X[i]], S[Y[i]]);
        bool xin = mis.find(X[i]) != mis.end();
        bool yin = mis.find(Y[i]) != mis.end();
        if(xin && !yin){
            mis.erase(X[i]);
            mis.insert(Y[i]);
        }
        if(yin && !xin){
            mis.erase(Y[i]);
            mis.insert(X[i]);
        }
        bool done = false;
        if(mis.empty()){
            P[i] = 0;
            Q[i] = 0;
        }else{
            int j = *(mis.begin());
            int k = Sinv[A[j]];
        /*    for(int it = 0; it < N; it++){
                cerr << S[it] << " ";
            }
            cerr << endl;
            cerr << j << " " << k << endl;*/
            P[i] = j;
            Q[i] = k;
            swap(Sinv[S[j]], Sinv[S[k]]);
            swap(S[j], S[k]);
            if(S[j] == A[j]){
                mis.erase(j);
            }else{
                mis.insert(j);
            }
            if(S[k] == A[k]){
                mis.erase(k);
            }else{
                mis.insert(k);
            }
        }
    }
    for(int i = 0; i < N; i++){
        assert(S[i] == i);
    }
    for(int i = 0; i < M; i++){
        swap(tmp[X[i]], tmp[Y[i]]);
        swap(tmp[P[i]], tmp[Q[i]]);
        //cerr << X[i] << " " << Y[i] << "   ";
        //cerr << P[i] << " " << Q[i] << "   ";
        /*for(int j = 0; j < N; j++){
            cerr << tmp[j] << " ";
        }
        cerr << endl;*/
    }
    for(int i = 0; i < N; i++){
        assert(tmp[i] == i);
    }
    //cerr << "ASSERTS OK" << endl;
    /*for(int i = 0; i < N; i++){
        cerr << A[i] << " ";
    }
    cerr << endl;
    for(int i = 0; i < N; i++){
        cerr << S[i] << " ";
    }
    cerr << endl;*/
    return M;
}

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