Submission #1235570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235570		tapilyoca	Monster Game (JOI21_monster)	C++20	0 / 100	60 ms	412 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;

    for(int i = 0 ; i < N; i++) {
        ll winCount = 0;
        for(int j = 0; j < N; j++) {
            if(i == j) continue;
            if(Query(i,j)) winCount++;
        }
        // cerr << i << " " << winCount << endl;
        if(winCount == 1) couldBeWeak.pb(i);
        else if(winCount == N-2) couldBeStrong.pb(i);
        else ans[i] = winCount;
    }

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