Submission #552052

#	Time	Username	Problem	Language	Result	Execution time	Memory
552052		RaresFelix	Monster Game (JOI21_monster)	C++17	88 / 100	136 ms	1828 KiB

monster

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

using namespace std;
namespace da {
    int query_count = 0;
}
namespace {
    map<pair<int, int>, bool> R;
}  // namespace
bool cmp(int st, int dr) {
    if(R.count({st, dr})) return R[{st, dr}];
    else {
        ++da::query_count;
        R[{dr, st}] = !(R[{st, dr}] = Query(st, dr));
        return R[{st, dr}];
    }
}
bool is_cand(int p, int n) {
    int nr = 0;
    for(int i = 0; i < n; ++i)
        if(i != p) nr += cmp(p, i);
    return nr == 1;
}
using vi = vector<int>;
void mrg_srt(vi &O, vi &tmp, int st, int dr) {
    if(st == dr) return;
    int mij = (st + dr) >> 1;
    mrg_srt(O, tmp, st, mij);
    mrg_srt(O, tmp, mij + 1, dr);
    int p1 = st, p2 = mij + 1, pf = st;
    while(p1 <= mij && p2 <= dr) 
        tmp[pf++] = cmp(O[p1], O[p2]) ? O[p2++] : O[p1++];
    while(p1 <= mij) tmp[pf++] = O[p1++];
    while(p2 <= dr) tmp[pf++] = O[p2++];
    for(int i = st; i <= dr; ++i) O[i] = tmp[i];
}
vector<int> Solve(int n) {
    vector<int> O(n), Tmp(n);
    for(int i = 0; i < n; ++i) O[i] = i;
    mrg_srt(O, Tmp, 0, n - 1);
    //printf("Sort Init: %d\n", da::query_count);
    vector<int> OC;
    for(int i = 0; i < 2; ++i) if(is_cand(O[i], n)) OC.push_back(O[i]);
    int lgp = 2;
    for(int i = 0; i < n - 2; ++i) {
        if(cmp(O[i], O[i + 2]))
            lgp = i + 2;
        else break;
    }
    for(int i = lgp; i >= max(lgp-2, 2); --i) if(is_cand(O[i], n)) OC.push_back(O[i]);


    int zero;
    if(OC.size() == 2)
        zero = cmp(OC[0], OC[1]) ? OC[0] : OC[1];
    else zero = OC[0];
    //printf("Det0: %d\n", da::query_count);

    vector<int> NewO;
    NewO.push_back(zero);
    for(int i = 0; i < n; ++i)
        if(O[i] != zero) NewO.push_back(O[i]); 
    int start = 1;
    for(int i = 1; i < n; ++i) {
        if(cmp(NewO[start-1], NewO[i])) { // urmatorul
            reverse(NewO.data() + start, NewO.data() + i + 1);
            start = i + 1;
        }
    }
    vector<int> R(n);
    //printf("Fin: %d\n", da::query_count);
//    for(int i = 0; i < n; ++i) cerr << R[i] << " "; cerr << "\n";
    //for(int i = 0; i < n; ++i) cerr << NewO[i] << " "; cerr << "\n";
    for(int i = 0; i < n; ++i) R[NewO[i]] = i;
    return R;
}

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