| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 705046 | MtSaka | Monster Game (JOI21_monster) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rrep(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;i--)
#define all(x) begin(x),end(x)
using ll=long long;
using namespace std;
using ull=unsigned long long;
template<typename T,typename U>
inline bool chmax(T&a,const U&b){return (a<b)?a=b,true:false;}
template<typename T,typename U>
inline bool chmin(T&a,const U&b){return (a>b)?a=b,true:false;}
#include "monster.h"
map<pair<int,int>,bool>mp;
bool ask(int a,int b){
if(mp.count({a,b}))return mp[{a,b}];
if(mp.count({b,a}))return mp[{b,a}];
return mp[{a,b}]=Query(a,b);
}
void merge(vector<int>&v){
if(v.size()==1)return;
int mid=v.size()/2;
vector<int>l(v.begin(),v.begin()+mid),r(v.begin()+mid,v.end());
merge(l),merge(r);
int i=0,j=0;
rep(k,0,v.size()){
if(i==l.size())v[k]=r[j++];
else if(j==r.size())v[k]=l[i++];
else if(ask(l[i],r[j]))v[k]=r[j++];
else v[k]=l[i++];
}
return;
}
int sol2(const vector<int>&id){
int n=id.size();
vector<int>cnt(n,0);
vector<vector<int>>a(n,vector<int>(n,0));
rep(i,0,n)rep(j,i+1,n){
bool f=ask(id[i],id[j]);
if(f)cnt[i]++;
else cnt[j]++;
a[i][j]=f;
a[j][i]=!f;
}
rep(i,0,n)if(cnt[i]==1){
rep(j,i+1,n)if(cnt[j]==1){
if(a[i][j])return i
else return j;
break;
}
return i;
break;
}
return -1;
}
vector<int>Solve(int n){
vector<int>id(n);
iota(id.begin(),id.end(),0);
merge(id);
vector<int>tmp(id.begin(),id.begin()+min(10,n));
int mi=sol2(tmp);
int start=id[mi];
id.erase(id.begin()+mi);
id.insert(id.begin(),start);
rep(i,1,n){
ll j=i;
while(j<n&&ask(id[j],start))j++;
reverse(id.begin()+i,id.begin()+min(j+1,n));
if(j==n)break;
start=v[j];
i=j;
}
vector<int>ret(n);
rep(i,0,n)ret[id[i]]=i;
return ret;
}