Submission #1248563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248563		KindaGoodGames	Sorting (IOI15_sorting)	C++20	20 / 100	1 ms	584 KiB

sorting

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

using namespace std;

#define pii pair<int,int>
vector<pii> swaps;
vector<pii> evil;
vector<int> arr;

int n;
vector<pii> insertion_sort(vector<int> arr, vector<int> fin, int m){

    vector<int> pos(n);
    vector<int> posF(n);

    for(int i = 0; i < n; i++){
        pos[arr[i]] = i; 
        posF[fin[i]] = i; 
    }

    auto doSwap = [&](int a, int b){
        swap(arr[a], arr[b]);
        pos[arr[a]] = a;
        pos[arr[b]] = b;   
    };
    
    vector<pii> ops;
    for(int i = 0; i < n; i++){
        if (ops.size() > m) break;
        if(fin[i] == i) continue;
        doSwap(evil[ops.size()].first,evil[ops.size()].second);
        
        // element that is currently at the position of i
        int oth = fin[posF[i]];
        int p = fin[i];

        doSwap(pos[oth],pos[p]);
        ops.push_back({pos[oth],pos[p]});

        swap(fin[i], fin[posF[i]]);
        posF[fin[posF[i]]] = posF[i];   
        posF[fin[i]] = i;


    }
    return ops;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n = N;
	int ops = 0;
	arr.resize(N);
    evil.resize(M);
    for(int i = 0; i < M; i++){
        evil[i] = {X[i], Y[i]};
    }
	for(int i = 0; i < n; i++){
		arr[i] = S[i];
	}
    
    vector<int> cur = arr; 
    int l = 0, r = M;
    int b = M;
    while(l <= r){
        int mid = (l+r)/2;
        cur = arr;
        for(int i = 0; i < mid; i++){
            swap(cur[evil[i].first], cur[evil[i].second]); 
        }

        auto moves = insertion_sort(arr,cur, mid);
        if(moves.size() <= mid){  
            b = min(b, mid); 
            r = mid-1;
        }else{
            l = mid+1;
        } 
    } 

    cur = arr;
    for(int i = 0; i < b; i++){
        swap(cur[evil[i].first], cur[evil[i].second]); 
    }
    vector<pii> moves = insertion_sort(arr,cur,b);
    for(int j = 0; j < moves.size(); j++){
        P[j] = moves[j].first;
        Q[j] = moves[j].second;
    }
    for(int j = moves.size(); j <= b-1; j++){
        P[j] = Q[j] = 0;
    }

	return moves.size();
}

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