QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#203132 | #7510. Independent Set | ucup-team004# | RE | 1ms | 3616kb | C++20 | 2.0kb | 2023-10-06 15:41:10 | 2023-10-06 15:41:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define pb push_back
const int N=4005;
int n,ans[N][N];
vector<int> ask(vector<int> v){
cout<<"? "<<v.size();
for(auto i:v)cout<<" "<<i;
cout<<endl;
vector<int> res=v;
for(auto &i:res)cin>>i;
return res;
}
vector<int> ask(vector<int> s1,vector<int> s2){
vector<int> tmp=s1;
for(auto i:s2)tmp.pb(i);
auto res=ask(tmp);
auto zzz=s2;
For(i,0,s2.size()-1){
int x=s2[i],tmp=res[i+s1.size()];
For(j,0,i-1)if(res[s1.size()+j]==0)tmp-=ans[s2[j]][s2[i]];
zzz[i]=tmp;
}
return zzz;
}
void solve(vector<int> s1,vector<int> s2,vector<int> s3){
if(s1.size()==0||s2.size()==0)return;
if(s1.size()==1){
For(o,0,s2.size()-1)ans[s2[o]][s1[0]]=ans[s1[0]][s2[o]]=s3[o]; return;
}
vector<int> ls1,rs1,ls2,rs2,ls3,rs3;
int mid=s1.size()/2;
For(i,0,mid-1)ls1.pb(s1[i]);
For(i,mid,s2.size()-1)rs1.pb(s1[i]);
auto t=ask(ls1,s2);
For(i,0,s2.size()-1)if(t[i]==0){
rs2.pb(s2[i]); rs3.pb(s3[i]);
}else if(t[i]==s3[i]){
ls2.pb(s2[i]); ls3.pb(s3[i]);
}else{
ls2.pb(s2[i]); ls3.pb(t[i]);
rs2.pb(s2[i]); rs3.pb(s3[i]-t[i]);
}
solve(ls1,ls2,ls3);
solve(rs1,rs2,rs3);
}
void solve(vector<int> v){
if(v.size()<=1)return;
auto res=ask(v);
vector<int> s1,s2;
For(i,0,v.size()-1){
if(res[i]==0)s1.pb(v[i]); else s2.pb(v[i]);
}
solve(s2);
solve(s1,s2,ask(s1,s2));
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cin>>n;
vector<int> v;
For(i,1,n)v.pb(i);
solve(v);
For(i,1,n){
ans[i][i]=ask({i,i})[1];
}
vector<pair<int,int>> sb;
For(i,1,n)For(j,i,n)For(k,1,ans[i][j])sb.pb(make_pair(i,j));
cout<<"! "<<sb.size();
for(auto i:sb)cout<<" "<<i.first<<" "<<i.second;
cout<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3616kb
input:
4 0 2 1 0 0 0 0 0 0 0 2 1 0 2 1 0 0 0 0 0 0 0 1
output:
? 4 1 2 3 4 ? 2 2 3 ? 2 2 3 ? 4 1 4 2 3 ? 3 1 2 3 ? 2 1 1 ? 2 2 2 ? 2 3 3 ? 2 4 4 ! 4 1 2 1 2 1 3 4 4
result:
ok Ok, Accepted!
Test #2:
score: -100
Runtime Error
input:
4000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 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 1 0 0 0 0 2 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 2 1 0 1 0 0 0 0 1 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 1 0 0 0...
output:
? 4000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...