Codeforces Round #427 (Div. 2), problem: (E) The penguin’s game Solution In C/C++

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int N=1010;
int n,x,y,bit,ans;
int cnta,cntb;
int a[N],b[N];
int ans1,ans2;

int gao(int *a,int l,int r){
if (r-l+1==0) return 0;
printf(“? %d “,r-l+1);
for (int i=l;i<=r;i++)
printf(“%d “,a[i]);
printf(“\n”);
fflush(stdout);
int res;
scanf(“%d”,&res);
return res;
}

int find(int *a,int cnt){
int l=1,r=cnt,ans=cnt;
while (l<r){
int mid=(l+r)>>1;
int res=gao(a,l,mid);
if (res==y || res==(x^y))
ans=mid,r=mid; else
ans=mid+1,l=mid+1;
}
return a[ans];
}

int main(){
// freopen(“a.in”,”r”,stdin);
scanf(“%d%d%d”,&n,&x,&y);
for (int i=0;i<=9;i++){
cnta=0;
for (int j=1;j<=n;j++)
if (j&(1<<i))
a[++cnta]=j;
int res=gao(a,1,cnta);
if (res==y || res==(x^y)){
ans|=1<<i;
bit=i;
}
}
cnta=cntb=0;
for (int i=1;i<=n;i++)
if (i&(1<<bit))
a[++cnta]=i; else
b[++cntb]=i;
if (cnta>cntb)
ans1=find(b,cntb); else
ans1=find(a,cnta);
ans2=ans1^ans;
if (ans1>ans2)
swap(ans1,ans2);
printf(“! %d %d\n”,ans1,ans2);
}

(Visited 36 times, 1 visits today)
By |2017-08-05T21:44:16+00:00August 5th, 2017|Categories: C/C++, Programming||0 Comments