oj.uz

Submission #552044

# Submission time Handle Problem Language Result Execution time Memory
552044 2022-04-22T09:42:31 Z RaresFelix Monster Game (JOI21_monster) C++17
0 / 100
 127 ms 3976 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 416 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 416 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Partially correct 127 ms 2144 KB Partially correct
2 Runtime error 126 ms 3976 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -