Submission #1355529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1355529		toast12	Sorting (IOI15_sorting)	C++20	54 / 100	76 ms	548 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    // subtasks 1-4
    int ans = M;
    vector<int> pos(N);
    for (int i = 0; i < N; i++) pos[S[i]] = i;
    for (int i = 0; i < M; i++) {
        ans = i;
        if (is_sorted(S, S+N)) break;
        swap(pos[S[X[i]]], pos[S[Y[i]]]);
        swap(S[X[i]], S[Y[i]]);
        if (is_sorted(S, S+N)) {
            ans = i+1;
            break;
        }
        vector<int> v(N);
        for (int j = 0; j < N; j++) v[j] = S[j];
        for (int j = i+1; j < M; j++) swap(v[X[j]], v[Y[j]]);
        for (int j = 0; j < N; j++) {
            if (v[j] != j) {
                int x = pos[j];
                int y = pos[v[j]];
                swap(pos[S[x]], pos[S[y]]);
                swap(S[x], S[y]);
                P[i] = x, Q[i] = y;
                break;
            }
        }
    }
	return ans;
}

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