Submission #1123123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123123		crafticat	The Collection Game (BOI21_swaps)	C++20	50 / 100	304 ms	424 KiB

swaps

#include <bits/stdc++.h>

using namespace std;
#define F0R(i, n) for (int i = 0; i < n;i++)
#define FOR(i, j, n) for (int i = j;i < n;i++)

template<typename T>
using V = vector<T>;
using vi = V<int>;
constexpr int INF = 1e9 + 7;
using pi = pair<int,int>;

void schedule(int, int);

std::vector<int> visit();

void answer(std::vector<int>);

void solve(int n, int v) {
    vi arr(n);
    F0R(i, n)
        arr[i] = i + 1;

    F0R(iter, v / 2) {
        for (int i = 0; i + 1< n; i+=2) {
            schedule(arr[i], arr[i + 1]);
        }
        vi res = visit();
        int step = 0;
        for (int i = 0; i + 1 < n; i+=2) {
            if (!res[step++]) swap(arr[i], arr[i + 1]);
        }

        for (int i = 1; i + 1 < n; i+=2) {
            schedule(arr[i], arr[i + 1]);
        }
        res = visit();
        step = 0;
        for (int i = 1; i + 1< n; i+=2) {
            if (!res[step++]) swap(arr[i], arr[i + 1]);
        }
    }

    answer(arr);
}

#if DEBUG
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <vector>


using namespace std;

void __attribute__((noreturn)) __attribute__((format(printf, 1, 2))) result(const char *msg, ...) {
    va_list args;
    va_start(args, msg);
    vfprintf(stderr, msg, args);
    fprintf(stderr, "\n");
    va_end(args);
    exit(0);
}

namespace {
    int N, V2, visits;
    set<int> queryIndices;
    vector<int> A, queryResult;
}

void schedule(int i, int j) {
    printf("schedule(%d, %d)\n", i, j);
    fflush(stdout);

    if (i < 1 || i > N || j < 1 || j > N || i == j)
        result("Invalid schedule");
    if (queryIndices.find(i) != queryIndices.end() || queryIndices.find(j) != queryIndices.end())
        result("Invalid schedule");
    queryIndices.insert(i);
    queryIndices.insert(j);

    int s = 0;
    if (s)
        swap(A[i], A[j]);
    queryResult.push_back(A[i] < A[j]);
}

vector<int> visit() {
    printf("visit(): {");
    for (int i = 0; i < (int)queryResult.size(); i++) {
        printf("%d", queryResult[i]);
        if (i + 1 != (int)queryResult.size())
            printf(", ");
    }
    printf("}\n");
    fflush(stdout);

    visits++;
    if (visits > V2)
        result("Out of visits");

    vector<int> res = queryResult;
    queryIndices.clear();
    queryResult.clear();
    return res;
}

void answer(vector<int> r) {
    printf("answer({");
    for (int i = 0; i < (int)r.size(); i++) {
        printf("%d", r[i]);
        if (i + 1 != (int)r.size())
            printf(", ");
    }
    printf("})\n");

    if ((int)r.size() != N)
        result("Invalid answer");

    for (int i = 0; i < N; i++) {
        if (r[i] < 1 || r[i] > N)
            result("Invalid answer");
        if (A[r[i]] != i + 1)
            result("Wrong answer");
    }

    result("Correct: %d visit(s) used", visits);
}

int main() {
    if (scanf("%d %d", &N, &V2) != 2 || N < 1 || V2 < 0)
        result("Invalid input");

    A.resize(N + 1);
    for (int i = 1; i <= N; i++) {
        int x;
        if (scanf("%d", &x) != 1 || x < 1 || x > N || A[x])
            result("Invalid input");
        A[x] = i;
    }

    solve(N, V2);

    result("No answer");
}
#endif

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3-1: 3 / 3
• Subtask 3-2: 2 / 2
• Subtask 4-1: 9 / 9
• Subtask 4-2: 6 / 6
• Subtask 5-1: 9 / 9
• Subtask 5-2: 6 / 6
• Subtask 6-1: 0 / 21
• Subtask 6-2: 0 / 14
• Subtask 7-1: 0 / 9
• Subtask 7-2: 0 / 6