| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1167566 | 8pete8 | Chameleon's Love (JOI20_chameleon) | C++20 | 0 ms | 0 KiB |
#include "chameleon.h"
#include <vector>
#include<iostream>
#define pb push_back
using namespace std;
namespace {
int variable_example = 1;
} // namespace
vector<int>adj[1001];
int done[1001],like[1001];
void Solve(int n){
if(n<=50&&0){
for(int i=1;i<=2*n;i++)for(int j=i+1;j<=2*n;j++){
if(Query({i,j})==1){
adj[i].pb(j),adj[j].pb(i);
}
}
}
else{
for(int i=1;i<=n;i++){
int last=n;
while(1){
int l=last+1,r=2*n,pos=3*n;
while(l<=r){
int mid=l+(r-l)/2;
vector<int>q;
for(int j=last+1;j<=mid;j++)q.pb(j);
q.pb(i);
if(Query(q)!=(mid-last+1))r=mid-1,pos=min(pos,mid);
else l=mid+1;
}
if(pos==3*n)break;
adj[i].pb(pos);
adj[pos].pb(i);
last=pos;
}
}
}
for(int i=1;i<=2*n;i++){
if(done[i])continue;
if(adj[i].size()==1){
Answer(i,adj[i][0]);
done[i]=1;
done[adj[i][0]]=1;
continue;
}
if(adj[i].size()==2)assert(0);
vector<int>ask(3,0);
for(int j=0;j<3;j++){
vector<int>q={i,adj[i][j],adj[i][(j+1)%3]};
ask[j]=Query(q);
}
for(int j=0;j<3;j++)if(ask[j]==2&&ask[(j-1+3)%3]==2){
like[i]=adj[i][j];
}
}
for(int i=1;i<=2*n;i++){
if(done[i])continue;
for(int j=0;j<3;j++)if(adj[i][j]!=like[i]&&i!=like[adj[i][j]]&&like[adj[i][j]]){
Answer(i,adj[i][j]);
done[adj[i][j]]=1;
}
}
}
/*
5
1 0 1 1 1 1 0 0 0 0
3 2 4 1 5 2 1 4 3 5
4 6 5 3 8 2 9 1 10 7
10
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
14 18 19 13 17 20 15 11 16 12 8 3 7 5 9 6 1 10 4 2
*/