| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1149266 | guagua0407 | Monster Game (JOI21_monster) | C++20 | 0 ms | 0 KiB |
#include "monster.h"
#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
namespace {
vector<int> ans;
mt19937 rng(time(NULL));
vector<int> res;
vector<vector<int>> rec;
} // namespace
int query(int a,int b){
if(rec[a][b]!=-1) return rec[a][b];
//cout<<a<<' '<<b<<'\n';
int val=Query(a,b);
rec[a][b]=val;
rec[b][a]=val^1;
return val;
}
bool comp(int a,int b){
return query(b,a);
}
void go1(vector<int>& a){
if((int)a.size()<=1) return;
int sz=(int)a.size();
vector<int> L,R;
for(int i=0;i<sz/2;i++){
L.push_back(a[i]);
}
for(int i=sz/2;i<sz;i++){
R.push_back(a[i]);
}
go1(L);
go1(R);
vector<int> tmp;
int l=0,r=0;
while(l<(int)L.size() or r<(int)R.size()){
if(r==(int)R.size()){
tmp.push_back(L[l]);
l++;
}
else if(l==(int)L.size()){
tmp.push_back(R[r]);
r++;
}
else{
if(query(R[r],L[l])){
tmp.push_back(L[l]);
l++;
}
else{
tmp.push_back(R[r]);
r++;
}
}
}
swap(tmp,a);
}
std::vector<int> Solve(int n) {
rec=vector<vector<int>>(n,vector<int>(n,-1));
ans=vector<int>(n,-1);
res.resize(n);
vector<int> a(n);
for(int i=0;i<n;i++){
a[i]=i;
}
shuffle(all(a),rng);
go1(a);
/*for(auto v:a){
cout<<v<<' ';
}
cout<<'\n';*/
int k=min(n,10);
vector<int> cnt(k);
for(int i=0;i<k;i++){
for(int j=0;j<k;j++){
if(i==j) continue;
cnt[i]+=query(a[i],a[j]);
}
}
vector<int> cand;
for(int i=0;i<k;i++){
if(cnt[i]<=1){
cand.push_back(i);
}
}
int zero;
if((int)cand.size()==1) zero=cand[0];
else if(cnt[cand[0]]==0) zero=cand[0];
else if(cnt[cand[1]]==0) zero=cand[1];
else{
if(query(a[cand[0]],a[cand[1]])) zero=cand[0];
else zero=cand[1];
}
//cout<<zero<<'\n';
reverse(a.begin(),a.begin()+zero+1);
int pos=zero;
while(pos<n-1){
int r=pos+1;
while(r<n and query(a[r],a[pos])){
r++;
}
reverse(a.begin()+pos+1,a.begin()+r+1);
pos=r;
// cout<<pos<<'\n';
}
for(int i=0;i<n;i++){
ans[a[i]]=i;
}
return ans;
}
/*
10
0 3 4 5 6 7 9 2 1 8
103
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102
*/