| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1340913 | aritro_ | 동굴 (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
//#include "cave.h"
using namespace std;
typedef long long ll;
#define endl '\n'
#define pb push_back
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
int n;
const int maxN=5000 + 15;
int a[maxN],b[maxN];
int con[maxN];
int tryCombination(int s[]);
void answer(int S[],int D[]);
bool open(int *p, int &k){
int a=tryCombination(p);
if(a==-1||a>k) return 1;
return 0;
}
void exploreCave(int n){
int s[n],d[n],ans[n];
for(int i=0;i<n;i++) s[i]=-1;
for(int i=0;i<n;i++){
vector<int> c;
for(int i=0;i<n;i++) if(s[i]==-1) c.push_back(i);
int p[n];
for(int i=0;i<n;i++){
if(s[i]==-1) p[i]=0;
else p[i]=s[i];
}
if(open(p,i)) ans[i]=0;
else ans[i]=1;
int st=0,end=c.size()-1,mid;
while(st<end){
for(auto x:c) p[x]=ans[i]^1;
mid=(st+end)/2;
for(int j=st;j<=mid;j++) p[c[j]]=ans[i];
if(open(p,i)) end=mid;
else st=mid+1;
}
d[c[st]]=i;
s[c[st]]=ans[i];
}
answer(s,d);
}
int tryCombination(int s[]){
for(int i=0;i<n;i++){
int ind=con[i];
if(s[con[i]]!=b[i]) return i;
}
return -1;
}
void answer(int S[],int D[]){
for(int i=0;i<n;i++) cout<<S[i]<<' ';
cout<<endl;
for(int i=0;i<n;i++) cout<<D[i]<<' ';
cout<<endl;
}
void solve(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i]>>b[i];
for(int i=0;i<n;i++) con[a[i]]=i;
//for(int i=0;i<n;i++) cout<<con[i]<<' ';
//cout<<endl;
//int test[4]={1,1,1,1};
//cout<<tryCombination(test)<<endl;
exploreCave(n);
int test[4]={0,1,1,1};
//cout<<endl;
//cout<<tryCombination(test)<<endl;
//cout<<con[0]<<' ';
return;
}
int32_t main(){
int t=1;
//cin>>t;
for(int tc=1;tc<=t;tc++){
//cout<<"Case "<<tc<<": ";
solve();
}
return 0;
}