欢迎光临
我们一直在努力

CF1583D Omkar and the Meaning of Life

每次回答都返回最前面的下标,所以我们求出p[n]的值,这样会很有用。

我们可以用n次查询操作来求出p[n]:想确定i是否为j可以这样判断,令a[i]=n,其余值都为j,这样如果p[i]为j,就会出现两个s值为j+n,也就是不为0的,所以返回不是0,p[i]就等于j。

用n次操作求出p[n]的代码(注:这里的a就是题目中的p):

for(int i=1;i<=n;i++){
printf("? ");
for(int j=1;j<=n;j++){
if(j==n) printf("%d ",n);
else printf("%d ",i);
}
printf("\\n");
cout.flush();
ll x;
scanf("%lld",&x);
if(x!=0){
a[n]=i;
break;
}
}

接着我们要对于1~n-1的这些值每个都用一次操作求出,已知p[n]=x,求取值为j的位置可以这样判断:令a[i]=j,其余都为x,若返回位置小于i,p[k]=j。

用n-1次操作救出剩下的n-1个数的代码:

for(int i=1;i<=n;i++){
if(a[n]==i) continue;
printf("? ");
for(int j=1;j<=n;j++){
if(j==n) printf("%d ",i);
else{
printf("%d ",a[n]);
}
}
printf("\\n");
cout.flush();
ll x;
scanf("%lld",&x);
a[x]=i;
}

完整代码(求赞):

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e2+5;
ll n,a[N];
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
printf("? ");
for(int j=1;j<=n;j++){
if(j==n) printf("%d ",n);
else printf("%d ",i);
}
printf("\\n");
cout.flush();
ll x;
scanf("%lld",&x);
if(x!=0){
a[n]=i;
break;
}
}
if(!a[n]) a[n]=n;
for(int i=1;i<=n;i++){
if(a[n]==i) continue;
printf("? ");
for(int j=1;j<=n;j++){
if(j==n) printf("%d ",i);
else{
printf("%d ",a[n]);
}
}
printf("\\n");
cout.flush();
ll x;
scanf("%lld",&x);
a[x]=i;
}
printf("! ");
for(int i=1;i<=n;i++) printf("%d ",a[i]);
printf("\\n");
cout.flush();
return ~(-1);
}

赞(0)
未经允许不得转载:171主机测评 » CF1583D Omkar and the Meaning of Life
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址