Submission #793861

#	Time	Username	Problem	Language	Result	Execution time	Memory
793861		PixelCat	Sorting (IOI15_sorting)	C++14	54 / 100	8 ms	576 KiB

sorting

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include "sorting.h"

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 200'000;

int val[MAXN + 10];
int pos[MAXN + 10];

int tmp[MAXN + 10];
bool check(int n, int lim, vector<pii> &ops) {
    For(i, 0, n - 1) tmp[i] = val[i];
    ops.clear();
    For(i, 0, n - 1) {
        while(tmp[i] != i) {
            if(sz(ops) == lim) return false;
            // For(j, 0, n - 1) cerr << tmp[j] << " ";
            // cerr << "--> ";
            // cerr << tmp[i] << ", " << tmp[tmp[i]] << "\n";
            ops.eb(tmp[i], tmp[tmp[i]]);
            swap(tmp[i], tmp[tmp[i]]);
        }
    }
    return true;
}

void out(int n) {
    cerr << "out:\n";
    cerr << "  "; For(i, 0, n - 1) cerr << val[i] << " \n"[i == n - 1];
    cerr << "  "; For(i, 0, n - 1) cerr << pos[i] << " \n"[i == n - 1];
}

int32_t findSwapPairs(int32_t N, int32_t S[], int32_t M, int32_t X[], int32_t Y[], int32_t P[], int32_t Q[]) {
    For(i, 0, N - 1) {
        val[i] = S[i];
        pos[val[i]] = i;
    }
    // out(N);
    For(i, 0, M - 1) {
        int p1 = X[i], p2 = Y[i];
        swap(pos[val[p1]], pos[val[p2]]);
        swap(val[p1], val[p2]);
        // For(j, 0, N - 1) cerr << val[j] << " \n"[j == N - 1];
        vector<pii> op;
        if(check(N, i + 1, op)) {
            For(j, sz(op), i) P[j] = Q[j] = 0;
            Forr(j, i, 0) {
                if(j < sz(op)) {
                    int v1 = op[j].F;
                    int v2 = op[j].S;
                    P[j] = (int32_t)pos[v1];
                    Q[j] = (int32_t)pos[v2];
                    swap(val[pos[v1]], val[pos[v2]]);
                    swap(pos[v1], pos[v2]);
                    // out(N);
                }
                p1 = X[j]; p2 = Y[j];
                swap(pos[val[p1]], pos[val[p2]]);
                swap(val[p1], val[p2]);
                // out(N);
            }
            return (int32_t)(i + 1);
        }
        // cerr << "\n";
    }
    assert(false);
    return 0;
}

/*

30421
10423
10243

*/

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