Submission #1052316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052316		Sacharlemagne	Monster Game (JOI21_monster)	C++17	95 / 100	61 ms	848 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
namespace {

bool example_variable;

}  // namespace
vi solveP(int l, int r) {
    if (l == r) return {l};
    vi lp = solveP(l,(l+r)/2), rp = solveP(1+(l+r)/2,r);
    vi ans;
    int p1 = 0, p2 = 0;
    while (p1 < lp.size() || p2 < rp.size()) {
        if (p1 < lp.size() && p2 < rp.size()) {
            if (!Query(lp[p1],rp[p2])) ans.push_back(rp[p2++]);
            else ans.push_back(lp[p1++]);
        }
        else if (p1 < lp.size()) ans.push_back(lp[p1++]);
        else ans.push_back(rp[p2++]);
    }
    return ans;
}
vector<int> badSolve(int N, vi ans) {
    map<int,int> v;
    for (int i = 0; i<N; ++i) {
        for (int j = i+1; j<N; ++j) {
            ++v[Query(ans[i],ans[j]) ? ans[i] : ans[j]];
        }
    }
    sort(ans.begin(), ans.end(), [&](int a, int b) {return v[a] < v[b];});
    if (!Query(ans[0], ans[1])) swap(ans[0], ans[1]);
    if (!Query(ans[N-2], ans[N-1])) swap(ans[N-2], ans[N-1]);
    return ans;
}
vi Solve(int N) {
    vi v = solveP(0,N-1);
    reverse(v.begin(), v.end());
    int k = min(N, 48);
    vi partial(v.begin(), v.begin()+k);
    int zero = badSolve(k,partial)[0];
    int ind = find(v.begin(), v.end(), zero)-v.begin();
    reverse(v.begin(), v.begin()+ind+1);
    while (ind < N-1) {
        int i = ind+1;
        while (Query(v[i],v[ind])) ++i;
        reverse(v.begin()+ind+1,v.begin()+i+1);
        ind = i;
    }
    vi ret(N); for (int i = 0; i<N; ++i) ret[v[i]] = i;
    return ret;
}

Compilation message (stderr)

monster.cpp: In function 'vi solveP(int, int)':
monster.cpp:15:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     while (p1 < lp.size() || p2 < rp.size()) {
      |            ~~~^~~~~~~~~~~
monster.cpp:15:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     while (p1 < lp.size() || p2 < rp.size()) {
      |                              ~~~^~~~~~~~~~~
monster.cpp:16:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         if (p1 < lp.size() && p2 < rp.size()) {
      |             ~~~^~~~~~~~~~~
monster.cpp:16:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         if (p1 < lp.size() && p2 < rp.size()) {
      |                               ~~~^~~~~~~~~~~
monster.cpp:20:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         else if (p1 < lp.size()) ans.push_back(lp[p1++]);
      |                  ~~~^~~~~~~~~~~
monster.cpp: At global scope:
monster.cpp:7:6: warning: '{anonymous}::example_variable' defined but not used [-Wunused-variable]
    7 | bool example_variable;
      |      ^~~~~~~~~~~~~~~~

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