Submission #1240177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240177		simplemind_31	Sorting (IOI15_sorting)	C++20	20 / 100	1 ms	580 KiB

sorting

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

#define PII pair<int, int>
#define MP make_pair
#define FI first
#define SE second

int sizeN;
vector<int> initialApples, adversaryX, adversaryY;
vector<PII> swapPlan;

// Check if we can finish in 'rounds' rounds, filling swapPlan
bool checkRounds(int rounds) {
    swapPlan.clear();
    swapPlan.resize(rounds, MP(0, 0));

    vector<int> plateAtSlot(sizeN), appleSlot(sizeN), currApples(sizeN);
    vector<int> slotOfPlate(sizeN), desiredSlot(sizeN);

    // Initialize current apples and appleSlot
    for (int i = 0; i < sizeN; ++i) {
        currApples[i] = initialApples[i];
        appleSlot[currApples[i]] = i;
        plateAtSlot[i] = i;
    }

    // Pre-simulate adversary's plate swaps
    for (int i = 0; i < rounds; ++i) {
        swap(plateAtSlot[adversaryX[i]], plateAtSlot[adversaryY[i]]);
    }
    // Build slotOfPlate and desiredSlot maps
    for (int slot = 0; slot < sizeN; ++slot) {
        slotOfPlate[plateAtSlot[slot]] = slot;
    }
    for (int plate = 0; plate < sizeN; ++plate) {
        desiredSlot[plate] = slotOfPlate[plate];
    }

    int nextApple = 0;
    for (int i = 0; i < rounds; ++i) {
        // Adversary swaps apples at slots
        int x = adversaryX[i], y = adversaryY[i];
        swap(currApples[x], currApples[y]);
        appleSlot[currApples[x]] = x;
        appleSlot[currApples[y]] = y;

        // Skip already-correct apples
        while (nextApple < sizeN &&
               appleSlot[nextApple] == desiredSlot[nextApple]) {
            ++nextApple;
        }
        if (nextApple == sizeN) break;

        // Swap the next mis-placed apple into its correct slot
        int from = appleSlot[nextApple];
        int to   = desiredSlot[nextApple];
        swapPlan[i] = MP(from, to);
        swap(currApples[from], currApples[to]);
        appleSlot[currApples[from]] = from;
        appleSlot[currApples[to]]   = to;
    }

    // Final check
    while (nextApple < sizeN &&
           appleSlot[nextApple] == desiredSlot[nextApple]) {
        ++nextApple;
    }
    return nextApple == sizeN;
}

// Main API: fill P[]/Q[] with up to M swaps, return number of rounds used
int findSwapPairs(int N, int S[], int M,
                  int X[], int Y[],
                  int P[], int Q[])
{
    sizeN = N;
    initialApples.clear();
    adversaryX.clear();
    adversaryY.clear();
    initialApples.resize(sizeN);
    adversaryX.resize(M);
    adversaryY.resize(M);

    for (int i = 0; i < sizeN; ++i) initialApples[i] = S[i];
    for (int i = 0; i < M; ++i) {
        adversaryX[i] = X[i];
        adversaryY[i] = Y[i];
    }

    int lo = -1, hi = M + 1;
    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if (checkRounds(mid)) hi = mid;
        else                lo = mid;
    }
    checkRounds(hi);
    for (int i = 0; i < hi; ++i) {
        P[i] = swapPlan[i].FI;
        Q[i] = swapPlan[i].SE;
    }
    return hi;
}

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