제출 #552044

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
552044		RaresFelix	Monster Game (JOI21_monster)	C++17	0 / 100	127 ms	3976 KiB

monster

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

using namespace std;

namespace {
    map<pair<int, int>, bool> R;
}  // namespace
bool cmp(int st, int dr) {
    if(R.count({st, dr})) return R[{st, dr}];
    else {
        R[{dr, st}] = !(R[{st, dr}] = Query(st, dr));
        return R[{st, dr}];
    }
}
struct ccmp {
    bool operator()(int st, int dr) {
        return !cmp(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;
}
vector<int> Solve(int n) {
    priority_queue<int, vector<int>, ccmp> P;
    for(int i = 0; i < n; ++i) P.push(i);
    vector<int> O;
    while(!P.empty()) O.push_back(P.top()), P.pop();
    reverse(O.begin(), O.end());
    vector<int> OC;
    for(int i = 0; i < 3; ++i) if(is_cand(O[i], n)) OC.push_back(O[i]);
    int lgp = 2;
    for(int i = 0; i < n - 3; ++i) {
        if(cmp(O[i], O[i + 2]))
            lgp = i + 2;
        else break;
    }
    for(int i = lgp; i >= max(lgp-2, 3); --i) if(is_cand(O[i], n)) OC.push_back(O[i]);

    assert(OC.size() == 2);

    int zero = cmp(OC[0], OC[1]) ? OC[0] : OC[1];

    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);
//    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: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75