QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#409711 | #7510. Independent Set | grass8cow | TL | 0ms | 4140kb | C++17 | 2.0kb | 2024-05-12 16:22:47 | 2024-05-12 16:22:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m,ct[5010][5010];
#define vi vector<int>
#define pb push_back
int All;
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);
}
All+=sz;
if(All>176000)assert(0);
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: 100
Accepted
time: 0ms
memory: 4140kb
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:
ok Ok, Accepted!
Test #2:
score: -100
Time Limit Exceeded
input:
4000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
? 2 1 1 ? 2 2 2 ? 2 3 3 ? 2 4 4 ? 2 5 5 ? 2 6 6 ? 2 7 7 ? 2 8 8 ? 2 9 9 ? 2 10 10 ? 2 11 11 ? 2 12 12 ? 2 13 13 ? 2 14 14 ? 2 15 15 ? 2 16 16 ? 2 17 17 ? 2 18 18 ? 2 19 19 ? 2 20 20 ? 2 21 21 ? 2 22 22 ? 2 23 23 ? 2 24 24 ? 2 25 25 ? 2 26 26 ? 2 27 27 ? 2 28 28 ? 2 29 29 ...