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);
}

#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);
}

More from author

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Related posts

Advertismentspot_img

Latest posts

Famed mountaineer Nirmal Purja, 43, among 10 climbers killed after avalanche in Pakistan

Tragedy in the Karakoram: Nirmal Purja Among 10 Lost in Avalanche In a devastating turn of events for the global mountaineering community, renowned high-altitude climber...

How Under Desk Storage Is Quietly Changing the Game

📢 As an Amazon Associate, I earn from qualifying purchases.There comes a point when you realise that tolerating a frustrating situation is costing you...

Has a woman ever mated with an ape?

Throughout history, urban legends, mythology, and speculative fiction have frequently explored the boundaries between humans and animals. One of the most persistent and sensationalized...

Want to stay up to date with the latest news?

We would love to hear from you! Please fill in your details and we will stay in touch. It's that simple!