Submission #528858

#	Time	Username	Problem	Language	Result	Execution time	Memory
528858		c28dnv9q3	Monster Game (JOI21_monster)	C++17	56 / 100	187 ms	408 KiB

monster

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

using namespace std;

void print(string pre, vector<int> a) {
    return;
    cout << pre << " ";
    for (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());
    int iA = 0;
    int iB = 0;
    for (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 (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 (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 (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) {
    vector<int> T = sort(10, 0, N);

    print("t", T);

    int x = findMin(N, T);
    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) {
            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;
}

Compilation message (stderr)

monster.cpp: In function 'void print(std::string, std::vector<int>)':
monster.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i = 0; i < a.size(); ++i) {
      |                     ~~^~~~~~~~~~
monster.cpp: In function 'std::vector<int> sort(int, int, int)':
monster.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i < c.size(); ++i) {
      |                     ~~^~~~~~~~~~
monster.cpp:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         if (iA < a.size() && iB < b.size()) {
      |             ~~~^~~~~~~~~~
monster.cpp:30:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         if (iA < a.size() && iB < b.size()) {
      |                              ~~~^~~~~~~~~~
monster.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             if (iA == a.size()) {
      |                 ~~~^~~~~~~~~~~
monster.cpp: In function 'int findMin(int, std::vector<int>)':
monster.cpp:59:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for (int j = 0; j < min.size(); ++j) if (i % N == min[j]) cont = true;
      |                         ~~^~~~~~~~~~~~
monster.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int i = 0; i < min.size(); ++i) {
      |                         ~~^~~~~~~~~~~~
monster.cpp:94:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for (int i = 0; i < min.size(); ++i) {
      |                         ~~^~~~~~~~~~~~

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