Submission #1248548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248548		KindaGoodGames	Sorting (IOI15_sorting)	C++20	20 / 100	18 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, int m){

    vector<int> pos(n);

    for(int i = 0; i < n; i++){
        pos[arr[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 = n-1; i >= 0; i--){
        if (ops.size() > m) break;
        if(arr[i] == i) continue;
        int p = pos[i];
        doSwap(i,p);

        ops.push_back({i,p});
        doSwap(evil[ops.size()-1].first,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, i);
        if(moves.size() <= 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]);
    }
    while(true){

    }
	return swaps.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