QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#409707 | #7510. Independent Set | grass8cow | WA | 1ms | 4020kb | C++17 | 1.9kb | 2024-05-12 16:20:45 | 2024-05-12 16:20:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m,ct[5010][5010];
#define vi vector<int>
#define pb push_back
vi Ask(vi a,int bd=-1){
printf("? %d ",a.size());
for(int x:a)printf("%d ",x);puts("");fflush(stdout);
int sz=a.size();
vi b;
for(int i=0;i<sz;i++){
int e;scanf("%d",&e);
if(bd!=-1){for(int j=bd;j<i;j++)e-=ct[a[j]][a[i]];}
b.pb(e);
}
return b;
}
#define pi pair<int,int>
#define mp make_pair
#define fi first
#define se second
void cdq(vi a,vector<pi>b){
if(b.empty())return;
int sa=a.size();
if(!sa)return;
if(sa==1){
for(pi o:b)ct[a[0]][o.fi]=ct[o.fi][a[0]]=o.se;
return;
}
vi cl,cr;int mi=(sa-1)/2;
for(int i=0;i<=mi;i++)cl.pb(a[i]);
for(int i=mi+1;i<sa;i++)cr.pb(a[i]);
vi a_=cl;int oi=cl.size(),bs=b.size();
for(pi x:b)a_.pb(x.fi);
vi E=Ask(a_,oi);
vector<pi>tl,tr;
for(int i=0;i<bs;i++){
if(E[oi+i])tl.pb(mp(b[i].fi,E[oi+i]));
if(E[oi+i]!=b[i].se)tr.pb(mp(b[i].fi,b[i].se-E[oi+i]));
}
cdq(cl,tl),cdq(cr,tr);
}
void sol(vi V){
if(V.size()<=1)return;
vi A,B,E=Ask(V);
int sz=V.size();
for(int i=0;i<sz;i++){
if(E[i])B.pb(V[i]);
else A.pb(V[i]);
}
sol(B);V.clear();
for(int x:A)V.pb(x);for(int x:B)V.pb(x);
int sa=A.size(),sb=B.size();
E=Ask(V,sa);
vector<pi>C;
for(int x:B){
int k=E[sa++];
if(k)C.pb(mp(x,k));
}
cdq(A,C);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
vi zh=Ask({i,i});
ct[i][i]=zh[1];
}
vector<int>V;for(int i=1;i<=n;i++)V.pb(i);
sol(V);
int ps=0;
for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)ps+=ct[i][j];
printf("!%d ",ps);
for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)while(ct[i][j]--)printf("%d %d ",i,j);
puts("");fflush(stdout);
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4020kb
input:
4 0 0 0 0 0 0 0 1 0 2 1 0 0 0 0 0 0 0 2 1 0 2 1
output:
? 2 1 1 ? 2 2 2 ? 2 3 3 ? 2 4 4 ? 4 1 2 3 4 ? 2 2 3 ? 2 2 3 ? 4 1 4 2 3 ? 3 1 2 3 !4 1 2 1 2 1 3 4 4
result:
wrong answer Bad request