QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#288279 | #7510. Independent Set | 1kri | WA | 1ms | 4064kb | C++14 | 2.5kb | 2023-12-22 13:21:36 | 2023-12-22 13:21:37 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int cnt[4005][4005];
vector<int> qry(vector<int> c){
int l=(int)c.size();
cout<<"? "<<l<<' ';
for (int i=0;i<l;i++)cout<<c[i]<<' ';
cout<<endl;
vector<int> ans(l);
for (int i=0;i<l;i++)cin>>ans[i];
return ans;
}
namespace QwQ{
vector<pair<int,int>> qwq[10005];
void init(){
for (int i=1;i<=10000;i++)qwq[i].clear();
return;
}
vector<pair<int,int>> ask(vector<int> c,vector<pair<int,int>> d){
int lc=(int)c.size(),ld=(int)d.size();
vector<pair<int,int>> ans(ld);
vector<int> awa;
for (int i=0;i<lc;i++)awa.push_back(c[i]);
for (int i=0;i<ld;i++)awa.push_back(d[i].first);
vector<int> ovo=qry(awa);
for (int i=0;i<ld;i++){
ans[i].first=d[i].first,ans[i].second=ovo[lc+i];
for (int j=0;j<i;j++)
if (ovo[lc+j]==0)
ans[i].second-=cnt[min(d[i].first,d[j].first)][max(d[i].first,d[j].first)];
}
return ans;
}
void work(int now,vector<int> c){
int l=(int)c.size();
if (l==0)return;
if (l==1){
for (int i=0;i<(int)qwq[now].size();i++)
cnt[min(c[0],qwq[now][i].first)][max(c[0],qwq[now][i].first)]=qwq[now][i].second;
return;
}
vector<int> cl,cr;
for (int i=0;i<l/2;i++)cl.push_back(c[i]);
for (int i=l/2;i<l;i++)cr.push_back(c[i]);
vector<pair<int,int>> awa=ask(cl,qwq[now]);
for (int i=0;i<(int)qwq[now].size();i++){
if (awa[i].second>0)qwq[now*2].push_back(awa[i]);
if (awa[i].second<qwq[now][i].second)
qwq[now*2+1].push_back(make_pair(awa[i].first,qwq[now][i].second-awa[i].second));
}
work(now*2,cl);
work(now*2+1,cr);
return;
}
}
void work(vector<int> c){
int l=(int)c.size();
if (l==0)return;
if (l==1){
cnt[c[0]][c[0]]=(qry({c[0],c[0]}))[1];
return;
}
vector<int> a,b;
vector<int> qwq=qry(c);
for (int i=0;i<l;i++)
if (qwq[i]==0)a.push_back(c[i]);
else b.push_back(c[i]);
work(b);
int la=(int)a.size(),lb=(int)b.size();
c.clear();
for (int i=0;i<la;i++)c.push_back(a[i]);
for (int i=0;i<lb;i++)c.push_back(b[i]);
qwq=qry(c);
QwQ::init();
for (int i=0;i<lb;i++)QwQ::qwq[1].push_back(make_pair(b[i],qwq[la+i]));
QwQ::work(1,a);
return;
}
int main(){
int n;
cin>>n;
vector<int> c;
for (int i=1;i<=n;i++)c.push_back(i);
work(c);
int m=0;
for (int i=1;i<=n;i++)
for (int j=i;j<=n;j++)
m+=cnt[i][j];
cout<<"! "<<m<<' ';
for (int i=1;i<=n;i++)
for (int j=i;j<=n;j++)
while(cnt[i][j]--)cout<<i<<' '<<j<<' ';
cout<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4064kb
input:
4 0 2 1 0 0 0 0 0 0 0 0 2 1 0 2 1
output:
? 4 1 2 3 4 ? 2 2 3 ? 2 2 3 ? 1 2 ? 4 1 4 2 3 ? 3 1 2 3 ! 3 1 2 1 2 1 3
result:
wrong answer Wrong graph