Submission #1248557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248557		KindaGoodGames	Sorting (IOI15_sorting)	C++20	0 / 100	22 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;
        
        // 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[i]] = i;
        posF[fin[posF[i]]] = posF[i];   


        doSwap(arr[evil[ops.size()-1].first],arr[evil[ops.size()-1].second]);
    }
    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; 
    for(int i = 0; i <= M; i++){
        auto moves = insertion_sort(arr,cur, i);
        if(moves.size() <= i){ 
            insertion_sort(arr,cur, i);
            for(int j = 0; j < moves.size(); j++){
                P[j] = moves[j].first;
                Q[j] = moves[j].second;
            }
            for(int j = moves.size(); j <= i; j++){
                P[j] = Q[j] = 0;
            }
            return i;
        }
        
        if(i == M) break;
        swap(cur[evil[i].first], cur[evil[i].second]);
    } 
	return swaps.size();
}

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