Submission #530771

#	Time	Username	Problem	Language	Result	Execution time	Memory
530771		c28dnv9q3	Monster Game (JOI21_monster)	C++17	10 / 100	254 ms	6108 KiB

monster

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

using namespace std;

const int len = 12;

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

int higher[1 << len];
map<pair<int, int>, int> quer;

bool cmp(int a, int b, int N) {
    if (a >= N) return true;
    if (b >= N) return false;
    //cout << a << " " << b << "\n";
    bool q = Query(a, b);
    if (q) higher[a]++; else higher[b]++;
    return q;
}

bool compare(int a, int b, int N) {
    if (quer[{a, b}] != 0) return quer[{a, b}] == 2;
    bool q = cmp(a, b, N);
    quer[{a, b}] = q ? 2 : 1;
    quer[{b, a}] = q ? 1 : 2;
    return q;
}

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> low;

    for (int i = 0; i < N; ++i) {
        if (higher[i] <= 3) low.push_back(i);
    }

    print("possible: ", low);

    int ii;
    for (int i = 0; i < low.size(); ++i) {
        ii = i + 1;
        while (ii < low.size() && higher[i] <= 3) {
            if (higher[ii] <= 3) compare(low[i], low[ii], N);
            ii++;
        }
    }

    vector<int> possible;
    for (int i = 0; i < low.size(); ++i) {
        if (higher[low[i]] <= 3) possible.push_back(low[i]);
    }

    print("possible: ", possible);

    for (int i = 0; i < possible.size(); ++i) {
        for (int j = i + 1; j < possible.size(); ++j) {
            compare(possible[i], possible[j], N);
        }
    }

    vector<int> min;
    for (int i = 0; i < possible.size(); ++i) {
        if (higher[possible[i]] == 1) min.push_back(possible[i]);
    }

    print("last: ", min);

    //for (int i = 0; i < N; ++i) cout << higher[i]; cout << "\n";

    return compare(min[0], min[1], N) ? min[0] : min[1];
}

std::vector<int> Solve(int N) {
    vector<int> T = sort(len, 0, N);

    int ind = -1;
    int x = findMin(N);
    for (int i = 0; i < N; ++i) {
        if (T[i] == x) ind = i;
    }
    if (ind == -1) return {};
    rev(T, 0, ind);

    for (int s = ind; s < N - 1;) {
        for (int i = s + 1; i < N; ++i) {
            if (compare(T[s], T[i], N)) {
                rev(T, s + 1, i);
                s = i;
                break;
            }
            if (i == N - 1) return {};
        }
    }

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

    return erg;
}

Compilation message (stderr)

monster.cpp: In function 'void print(std::string, std::vector<int>)':
monster.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int i = 0; i < a.size(); ++i) {
      |                     ~~^~~~~~~~~~
monster.cpp: In function 'std::vector<int> sort(int, int, int)':
monster.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i < c.size(); ++i) {
      |                     ~~^~~~~~~~~~
monster.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if (iA < a.size() && iB < b.size()) {
      |             ~~~^~~~~~~~~~
monster.cpp:46:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if (iA < a.size() && iB < b.size()) {
      |                              ~~~^~~~~~~~~~
monster.cpp:53:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             if (iA == a.size()) {
      |                 ~~~^~~~~~~~~~~
monster.cpp: In function 'int findMin(int)':
monster.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i = 0; i < low.size(); ++i) {
      |                     ~~^~~~~~~~~~~~
monster.cpp:81:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         while (ii < low.size() && higher[i] <= 3) {
      |                ~~~^~~~~~~~~~~~
monster.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i = 0; i < low.size(); ++i) {
      |                     ~~^~~~~~~~~~~~
monster.cpp:94:23: 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 < possible.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~
monster.cpp:95:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for (int j = i + 1; j < possible.size(); ++j) {
      |                             ~~^~~~~~~~~~~~~~~~~
monster.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (int i = 0; i < possible.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~

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