Submission #1240170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240170		simplemind_31	Sorting (IOI15_sorting)	C++20	20 / 100	1 ms	328 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[]){
	vector<int> a(N), inv_a(N);
    // Apples b[p] = apple on plate p
    vector<int> b(N);
	for(int i=0;i<N;i++){
		b[i]=S[i];
	}
    for(int i = 0; i < N; i++){
        a[i] = i;
        inv_a[i] = i;
    }

    // Function to check feasibility for t rounds
    auto can = [&](int t){
        // copy plates
        vector<int> ca = a;
        for(int i = 0; i < t; i++) swap(ca[X[i]], ca[Y[i]]);
        // build pi: pi[i] = apple at slot i
        vector<int> pi(N);
        for(int i = 0; i < N; i++) pi[i] = b[ca[i]];
        vector<bool> vis(N, false);
        int cycles = 0;
        for(int i = 0; i < N; i++){
            if(!vis[i]){
                cycles++;
                int x = i;
                while(!vis[x]){
                    vis[x] = true;
                    x = pi[x];
                }
            }
        }
        // swaps needed = N - cycles
        return (N - cycles) <= t;
    };

    // binary search minimum t
    int lo = 0, hi = M, mid, best = M;
    while(lo <= hi){
        mid = (lo + hi) / 2;
        if(can(mid)){
            best = mid;
            hi = mid - 1;
        } else lo = mid + 1;
    }

    // simulate adversary fully for best rounds
    for(int i = 0; i < best; i++){
        swap(a[X[i]], a[Y[i]]);
        inv_a[a[X[i]]] = X[i];
        inv_a[a[Y[i]]] = Y[i];
    }
    // build final pi
    vector<int> pi(N);
    for(int i = 0; i < N; i++) pi[i] = b[a[i]];
    vector<bool> vis(N, false);
    vector<pair<int,int>> ops;
    // decompose into cycles and gather swaps
    for(int i = 0; i < N; i++){
        if(!vis[i]){
            vector<int> cyc;
            int x = i;
            while(!vis[x]){
                vis[x] = true;
                cyc.push_back(x);
                x = pi[x];
            }
            // break cycle of length l: swaps (cyc[0],cyc[j]) for j=1..l-1
            for(size_t j = 1; j < cyc.size(); j++){
                int u = cyc[0], v = cyc[j];
                // swap apples on plates a[u], a[v]
                ops.emplace_back(a[u], a[v]);
                swap(b[a[u]], b[a[v]]);
            }
        }
    }
    // fill remaining with dummy swaps
    while((int)ops.size() < best) ops.emplace_back(0, 0);

    // output
	for(int i=0;i<best;i++){
		P[i]=ops[i].first;
		Q[i]=ops[i].second;
	}
	return best;
    /*cout << best << '\n';
    for(int i = 0; i < best; i++){
        cout << ops[i].first << " " << ops[i].second << "\n";
    }*/
}

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