Submission #1235572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235572		tapilyoca	Monster Game (JOI21_monster)	C++20	10 / 100	58 ms	408 KiB

monster

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

using namespace std;

template<typename T>
using vec = vector<T>;
using ll = long long;
using vll = vec<ll>;
#define pb push_back

std::vector<int> Solve(int N) {
    vec<int> ans(N,0);

    vec<int> couldBeWeak, couldBeStrong;
    vec<int> winCount(N,0);

    for(int i = 0 ; i < N; i++) {
        for(int j = i+1; j < N; j++) {
            if(Query(i,j)) {
                winCount[i]++;
            } else {
                winCount[j]++;
            }
        }
        // cerr << i << " " << winCount << endl;
    }

    for(int i = 0; i < N; i++) {
        if(winCount[i] == 1) couldBeWeak.pb(i);
        else if(winCount[i] == N-2) couldBeStrong.pb(i);
        else ans[i] = winCount[i];
    }

    bool test = Query(couldBeWeak[0], couldBeWeak[1]);
    ans[couldBeWeak[0]] = 0;
    ans[couldBeWeak[1]] = 1;
    if(!test) swap(ans[couldBeWeak[0]], ans[couldBeWeak[1]]);

    test = Query(couldBeStrong[0], couldBeStrong[1]);
    ans[couldBeStrong[0]] = N-2;
    ans[couldBeStrong[1]] = N-1;
    if(!test) swap(ans[couldBeStrong[0]],ans[couldBeStrong[1]]);

    for(int &x : ans) cerr << x << " ";
    cerr << endl;

    return ans;
}

/* 

str 0 => wc 1
str 1 => wc 1
str 2 => wc 2
str 3 => wc 3

...

str n-2 => wc n-2
str n-1 => wc n-2

*/

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