#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define rep(x,a,b) for (int x=int(a);x<=(int)(b);x++)
#define drp(x,a,b) for (int x=int(a);x>=(int)(b);x–)
#define cross(x,a) for (int x=hd[a];~x;x=nx[x])
#define ll long long
#define inf (1<<29)
#define pii pair<int,int>
#define pdd pair<double,double>
#define mk(a,b) make_pair(a,b)
#define fs first
#define sc second
#define pb push_back
#define VI vector<int>
#define VS vector<string>
using namespace std;
inline ll rd(){
ll x=0;int ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!=’-‘)&&(ch!=EOF)) ch=getchar();
if (ch==’-‘){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-‘0’;ch=getchar();}
return x*f;
}
inline void rt(ll x){
if (x<0) putchar(‘-‘),x=-x;
if (x>=10) rt(x/10),putchar(x%10+’0′);
else putchar(x+’0′);
}
const int maxn=2005;
int n,nc;
int hd[maxn],nx[maxn<<1],to[maxn<<1],cnt;
void addedge(int u,int v){
to[cnt]=v;nx[cnt]=hd[u];hd[u]=cnt++;
to[cnt]=u;nx[cnt]=hd[v];hd[v]=cnt++;
}
int pa[maxn],ls[maxn],rs[maxn],ez[maxn];
int cen,ms[maxn],size[maxn];
int del[maxn],allsize,nwk;
void getcenter(int u,int fa){
size[u]=1;ms[u]=0;
cross(i,u){
int v=to[i];
if (v==fa||del[v]) continue;
getcenter(v,u);
size[u]+=size[v];
ms[u]=max(ms[u],size[v]);
}
ms[u]=max(ms[u],allsize-size[u]);
if (u>n&&(!cen||ms[u]<ms[cen])) cen=u;
}
char ans[5];
void divide(int u){
cen=0;getcenter(u,0);u=cen;
del[u]=1;
printf(“%d %d %d\n”,ez[ls[u]],ez[rs[u]],nwk);
fflush(stdout);
scanf(“%s”,ans);
if (ans[0]==’X’){
if ((!~pa[u])||del[pa[u]]){
++nc;
if (~pa[u]){
pa[nc]=pa[u];
if (ls[pa[u]]==u) ls[pa[u]]=nc;else rs[pa[u]]=nc;
}
pa[u]=pa[nwk]=nc;
ls[nc]=u;rs[nc]=ez[nc]=nwk;
}
else allsize=size[pa[u]]<size[u]?size[pa[u]]:allsize-size[u],divide(pa[u]);
}
else if (ans[0]==’Z’){
if (ls[u]<=n||del[ls[u]]){
++nc;pa[nc]=u;
ls[nc]=ls[u],rs[nc]=ez[nc]=nwk,pa[ls[u]]=nc,ls[u]=nc,pa[nwk]=nc;
}
else allsize=size[ls[u]]<size[u]?size[ls[u]]:allsize-size[u],divide(ls[u]);
}
else if (ans[0]==’Y’){
if (rs[u]<=n||del[rs[u]]){
++nc;pa[nc]=u;
rs[nc]=rs[u],ls[nc]=ez[nc]=nwk,pa[rs[u]]=nc,rs[u]=nc,pa[nwk]=nc;
}
else allsize=size[rs[u]]<size[u]?size[rs[u]]:allsize-size[u],divide(rs[u]);
}
}
int main(){
nc=n=rd();
rep(i,1,n) ez[i]=i;
memset(pa,-1,sizeof pa);
pa[1]=pa[2]=++nc,ls[nc]=ez[nc]=1,rs[nc]=2;
rep(v,3,n){
nwk=v,allsize=v*2-3;
memset(hd,-1,sizeof hd);cnt=0;
rep(i,1,v-1) addedge(pa[i],i);
rep(i,n+1,nc) if (~pa[i]) addedge(pa[i],i);
memset(del,0,sizeof del);
divide(1);
}
puts(“-1”);
rep(i,1,n*2-1) rt(pa[i]),putchar(‘ ‘);putchar(‘\n’);
fflush(stdout);
}
Codeforces Round #409 (rated, Div. 1, based on VK Cup 2017 Round 2), problem: (E) Verifying Kingdom Solution In C/C++
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define rep(x,a,b) for (int x=int(a);x<=(int)(b);x++)
#define drp(x,a,b) for (int x=int(a);x>=(int)(b);x–)
#define cross(x,a) for (int x=hd[a];~x;x=nx[x])
#define ll long long
#define inf (1<<29)
#define pii pair<int,int>
#define pdd pair<double,double>
#define mk(a,b) make_pair(a,b)
#define fs first
#define sc second
#define pb push_back
#define VI vector<int>
#define VS vector<string>
using namespace std;
inline ll rd(){
ll x=0;int ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!=’-‘)&&(ch!=EOF)) ch=getchar();
if (ch==’-‘){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-‘0’;ch=getchar();}
return x*f;
}
inline void rt(ll x){
if (x<0) putchar(‘-‘),x=-x;
if (x>=10) rt(x/10),putchar(x%10+’0′);
else putchar(x+’0′);
}
const int maxn=2005;
int n,nc;
int hd[maxn],nx[maxn<<1],to[maxn<<1],cnt;
void addedge(int u,int v){
to[cnt]=v;nx[cnt]=hd[u];hd[u]=cnt++;
to[cnt]=u;nx[cnt]=hd[v];hd[v]=cnt++;
}
int pa[maxn],ls[maxn],rs[maxn],ez[maxn];
int cen,ms[maxn],size[maxn];
int del[maxn],allsize,nwk;
void getcenter(int u,int fa){
size[u]=1;ms[u]=0;
cross(i,u){
int v=to[i];
if (v==fa||del[v]) continue;
getcenter(v,u);
size[u]+=size[v];
ms[u]=max(ms[u],size[v]);
}
ms[u]=max(ms[u],allsize-size[u]);
if (u>n&&(!cen||ms[u]<ms[cen])) cen=u;
}
char ans[5];
void divide(int u){
cen=0;getcenter(u,0);u=cen;
del[u]=1;
printf(“%d %d %d\n”,ez[ls[u]],ez[rs[u]],nwk);
fflush(stdout);
scanf(“%s”,ans);
if (ans[0]==’X’){
if ((!~pa[u])||del[pa[u]]){
++nc;
if (~pa[u]){
pa[nc]=pa[u];
if (ls[pa[u]]==u) ls[pa[u]]=nc;else rs[pa[u]]=nc;
}
pa[u]=pa[nwk]=nc;
ls[nc]=u;rs[nc]=ez[nc]=nwk;
}
else allsize=size[pa[u]]<size[u]?size[pa[u]]:allsize-size[u],divide(pa[u]);
}
else if (ans[0]==’Z’){
if (ls[u]<=n||del[ls[u]]){
++nc;pa[nc]=u;
ls[nc]=ls[u],rs[nc]=ez[nc]=nwk,pa[ls[u]]=nc,ls[u]=nc,pa[nwk]=nc;
}
else allsize=size[ls[u]]<size[u]?size[ls[u]]:allsize-size[u],divide(ls[u]);
}
else if (ans[0]==’Y’){
if (rs[u]<=n||del[rs[u]]){
++nc;pa[nc]=u;
rs[nc]=rs[u],ls[nc]=ez[nc]=nwk,pa[rs[u]]=nc,rs[u]=nc,pa[nwk]=nc;
}
else allsize=size[rs[u]]<size[u]?size[rs[u]]:allsize-size[u],divide(rs[u]);
}
}
int main(){
nc=n=rd();
rep(i,1,n) ez[i]=i;
memset(pa,-1,sizeof pa);
pa[1]=pa[2]=++nc,ls[nc]=ez[nc]=1,rs[nc]=2;
rep(v,3,n){
nwk=v,allsize=v*2-3;
memset(hd,-1,sizeof hd);cnt=0;
rep(i,1,v-1) addedge(pa[i],i);
rep(i,n+1,nc) if (~pa[i]) addedge(pa[i],i);
memset(del,0,sizeof del);
divide(1);
}
puts(“-1”);
rep(i,1,n*2-1) rt(pa[i]),putchar(‘ ‘);putchar(‘\n’);
fflush(stdout);
}
