# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
895659 | Darren0724 | Monster Game (JOI21_monster) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "monster.h"
#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int n;
map<pair<int,int>,int> m;
inline int ask(int a,int b){
if(m.find({a,b})!=m.end()){
return m[{a,b}];
}
if(m.find({b,a})!=m.end()){
return m[{b,a}]^1;
}
return m[{a,b}]=Query(a,b);
}
vector<int> dc(int l,int r){\
if(r-l==1){
return vector<int>(1,l);
}
int m=(l+r)>>1;
vector<int> a = dc(l,m);
vector<int> b = dc(m,r);
vector<int> c;
int j=0;
int sz=b.size();
for(int i:a){
while(j<sz&&ask(i,b[j])){
c.push_back(b[j]);
j++;
}
c.push_back(i);
}
while(j<sz){
c.push_back(b[j]);
j++;
}
return c;
}
vector<int> Solve(int n1) {
n=n1;
vector<int> v = dc(0,n);
vector<int> ans(n),t(n);
int cnt=0;
for(int i=0;i<n-1;i++){
cnt+=ask(v[n-1],v[i]);
}
int i=n-1;
for(;cnt<n;cnt++,i--){
t[i]=cnt;
}
int last=n-1;
while(i>=0){
int rec=i;
while(!ask(v[i],v[last])){
i--;
}
last=rec;
cnt=rec;
for(int j=i;j<=rec;j++){
t[j]=cnt;
cnt--;
}
i--;
}
for(int i=0;i<n;i++){
ans[v[i]]=t[i];
}
return ans;
}
/*
6
1 3 5 0 4 2
*/