QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#409711#7510. Independent Setgrass8cowTL 0ms4140kbC++172.0kb2024-05-12 16:22:472024-05-12 16:22:48

Judging History

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

  • [2024-05-12 16:22:48]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:4140kb
  • [2024-05-12 16:22:47]
  • 提交

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 ...

result: