Submission #496099

#	Time	Username	Problem	Language	Result	Execution time	Memory
496099		Jarif_Rahman	Monster Game (JOI21_monster)	C++17	98 / 100	112 ms	4288 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

vector<vector<int>> QQ;
bool query(int a, int b){
    if(a > b){
        if(QQ[b][a] == -1) QQ[b][a] = Query(b, a);
        return !QQ[b][a];
    }
    else{
        if(QQ[a][b] == -1) QQ[a][b] = Query(a, b);
        return QQ[a][b];
    }
}

vector<int> Solve(int n){
    QQ = vector<vector<int>>(n, vector<int>(n, -1));
 
    vector<int> sth(n);
    for(int i = 0; i < n; i++) sth[i] = i;
    random_shuffle(sth.begin(), sth.end());
    stable_sort(sth.begin(), sth.end(), [&](int x, int y){
		return query(y, x);
    });
 
    auto win = [=](int x){
        vector<int> rt;
        for(int i = 0; i < n; i++) if(i != x && query(x, i)) rt.pb(i);
        return rt;
    };
 
    int z = -1, k = min(n, 10);
    vector<int> cnt(k, 0), ss(k);
    for(int i = 0; i < k; i++) ss[i] = i;
    for(int i = 0; i < k; i++){
        for(int j = 0; j < k; j++) if(i != j) cnt[i]+=query(sth[i], sth[j]);
    }
 
    sort(ss.begin(), ss.end(), [&](int x, int y){
        return cnt[x] < cnt[y];
    });
    if(query(sth[ss[0]], sth[ss[1]])) z = ss[0];
    else z = ss[1];
 
    reverse(sth.begin(), sth.begin()+z+1);
 
    for(;z+1 < n; z++){
        for(int i = z+1; i < n; i++) if(query(sth[z], sth[i])){
            reverse(sth.begin()+z+1, sth.begin()+i+1);
            z = i;
        }
    }
 
    vector<int> ans(n);
    for(int i = 0; i < n; i++) ans[sth[i]] = i;
    return ans;
}

Compilation message (stderr)

monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:32:10: warning: variable 'win' set but not used [-Wunused-but-set-variable]
   32 |     auto win = [=](int x){
      |          ^~~

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