Submission #1221786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221786		svtk	Monster Game (JOI21_monster)	C++20	10 / 100	59 ms	2316 KiB

monster

#include "monster.h"
#include <algorithm>
using namespace std;
using pii = pair<int, int>;

bool asked[1000][1000];
bool ans[1000][1000];
bool query(int a, int b){
    if(!asked[a][b]){
        asked[a][b] = true;
        asked[b][a] = true;
        ans[a][b] = Query(a, b);
        ans[b][a] = not ans[a][b];
    }
    return ans[a][b];
}

pii wins[1000];

std::vector<int> Solve(int N) {
    std::vector<int> T(N);

    for(int i=0; i<N; i++){
        wins[i] = {0, i};
    }

    for(int i=0; i<N; i++){
        for(int j=i+1; j<N; j++){
            if(query(i, j)){
                wins[i].first++;
            } else {
                wins[j].first++;
            }
        }
    }
    sort(wins, wins+N);
    for(int i=0; i<N; i++){
        T[wins[i].second] = i;
    }
    int l1 = wins[0].second;
    int l2 = wins[1].second;
    int w1 = wins[N-1].second;
    int w2 = wins[N-2].second;
    if(query(l2, l1)){
        T[l1] = 1;
        T[l2] = 0;
    }
    if(query(w1, w2)){
        T[w1] = N-2;
        T[w2] = N-1;
    }

    return T;
}

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