QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#409707#7510. Independent Setgrass8cowWA 1ms4020kbC++171.9kb2024-05-12 16:20:452024-05-12 16:20:46

Judging History

你现在查看的是最新测评结果

  • [2024-05-12 16:20:46]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4020kb
  • [2024-05-12 16:20:45]
  • 提交

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