Submission #1240178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240178		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, advX, advY;
vector<PII> swapPlan;

bool checkRounds(int rounds) {
    swapPlan.clear();
    swapPlan.resize(rounds, MP(0, 0));

    // slotMapping[i] = plate at slot i
    vector<int> slotMapping(sizeN);
    // currApple[i] = apple at slot i
    vector<int> currApple(sizeN);
    // positionOfApple[v] = slot of apple v
    vector<int> positionOfApple(sizeN);
    // platePosition[p] = slot of plate p
    vector<int> platePosition(sizeN);

    for (int i = 0; i < sizeN; ++i) {
        currApple[i] = initialApples[i];
        positionOfApple[currApple[i]] = i;
        slotMapping[i] = i;
        platePosition[i] = i;
    }

    int nextApple = 0;
    for (int i = 0; i < rounds; ++i) {
        int x = advX[i], y = advY[i];
        // adversary swaps plates
        swap(slotMapping[x], slotMapping[y]);
        platePosition[slotMapping[x]] = x;
        platePosition[slotMapping[y]] = y;

        // adversary swaps apples
        swap(currApple[x], currApple[y]);
        positionOfApple[currApple[x]] = x;
        positionOfApple[currApple[y]] = y;

        // skip correct apples
        while (nextApple < sizeN &&
               positionOfApple[nextApple] == platePosition[nextApple]) {
            ++nextApple;
        }
        if (nextApple == sizeN) break;

        // fix nextApple
        int from = positionOfApple[nextApple];
        int to   = platePosition[nextApple];
        swapPlan[i] = MP(from, to);
        swap(currApple[from], currApple[to]);
        positionOfApple[currApple[from]] = from;
        positionOfApple[currApple[to]]   = to;
    }

    // final check
    while (nextApple < sizeN &&
           positionOfApple[nextApple] == platePosition[nextApple]) {
        ++nextApple;
    }
    return nextApple == sizeN;
}

int findSwapPairs(int N, int S[], int M,
                  int X[], int Y[],
                  int P[], int Q[])
{
    sizeN = N;
    initialApples.assign(S, S + N);
    advX.assign(X, X + M);
    advY.assign(Y, Y + M);

    int lo = -1, hi = M + 1;
    while (lo + 1 < hi) {
        int mid = (lo + hi) >> 1;
        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