Submission #1248543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248543		KindaGoodGames	Sorting (IOI15_sorting)	C++20	20 / 100	29 ms	576 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> pos(n);

    for(int i = 0; i < n; i++){
        pos[arr[i]] = i; 
    }
    
    vector<pii> ops;
    for(int i = n-1; i >= 0; i--){
        if(arr[i] == i) continue;
        
        int p = pos[i];
        swap(arr[i], arr[pos[i]]);
        pos[arr[i]] = i;
        pos[arr[p]] = p;  

        ops.push_back({i,p});
    }
    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(cur);
        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