Submission #528855

#	Time	Username	Problem	Language	Result	Execution time	Memory
528855		c28dnv9q3	Monster Game (JOI21_monster)	C++17	0 / 100	0 ms	288 KiB

monster

#include "monster.h"
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

void print(string pre, vector<int> a) {
    cout << pre << " ";
    for (long unsigned int i = 0; i < a.size(); ++i) {
        cout << a[i] << " ";
    }
    cout << "\n";
}

bool compare(int a, int b, int N) {
    if (a >= N) return true;
    if (b >= N) return false;
    return Query(a, b);
}

vector<int> sort(int l, int o, int N) {
    if (l == 0) return std::vector<int>{o};
    vector<int> a = sort(l - 1, o, N);
    vector<int> b = sort(l - 1, o + (1 << (l - 1)), N);
    vector<int> c(a.size() + b.size());
    long unsigned int iA = 0;
    long unsigned int iB = 0;
    for (long unsigned int i = 0; i < c.size(); ++i) {
        if (iA < a.size() && iB < b.size()) {
            if (compare(a[iA], b[iB], N)) {
                c[i] = b[iB++];
            } else {
                c[i] = a[iA++];
            }
        } else {
            if (iA == a.size()) {
                c[i] = b[iB++];
            } else {
                c[i] = a[iA++];
            }
        }
    }
    return c;
}

void rev(vector<int> &T, int a, int b) {
    for (int i = 0; i < (1 + b - a) / 2; ++i) {
        swap(T[a + i], T[b - i]);
    }
}

int findMin(int N, vector<int> T) {
    vector<int> min = vector<int>{0, 1};
    vector<int> nMin;
    bool cont;
    for (int i = 0; true; ++i) {
        cont = false;
        for (long unsigned int j = 0; j < min.size(); ++j) if (i % N == min[j]) cont = true;
        if (cont) continue;
        min.push_back(i % N);

        if (min.size() == 4) {
            int count[] = {0, 0, 0, 0};
            for (int j = 0; j < 4; ++j) {
                for (int k = j + 1; k < 4; ++k) {
                    if (Query(T[min[j]], T[min[k]])) {
                        count[k]++;
                    } else {
                        count[j]++;
                    }
                }
            }

            nMin = vector<int>();
            for (int j = 0; j < 4; ++j) {
                if (count[j] >= 2) nMin.push_back(min[j]);
            }
            min = nMin;

            if (i >= 2 * N) break;
        }
    }

    if (min.size() == 3) {
        int count[] = {0, 0, 0};
        for (long unsigned int i = 0; i < min.size(); ++i) {
            for (int j = 0; j < N; ++j) {
                if (min[i] == j) continue;
                if (Query(T[min[i]], T[j])) count[i]++;
            }
        }
        nMin = vector<int>();
        for (long unsigned int i = 0; i < min.size(); ++i) {
            if (count[i] == 1) nMin.push_back(min[i]);
        }
        min = nMin;
    }

    print("possible", min);

    return Query(T[min[0]], T[min[1]]) ? min[0] : min[1];
}

std::vector<int> Solve(int N) {
    cout << "start\n";

    vector<int> T = sort(5, 0, N);

    print("t", T);

    int x = findMin(N, T);
    cout << "min " << x << "\n";
    rev(T, 0, x);

    print("t", T);

    for (int s = x; s < N - 1;) {
        print("t", T);
        for (int i = s + 1; i < N; ++i) {
            cout << s << " " << i << "\n";
            if (Query(T[s], T[i])) {
                rev(T, s + 1, i);
                s = i;
                break;
            }
        }
    }

    vector<int> erg = vector<int>(N, 0);
    for (int i = 0; i < N; ++i) {
        erg[T[i]] = i;
    }

    print("t", T);

    print("erg", erg);

    return erg;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75