QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#80689 | #4218. Hidden Graph | Crysfly | RE | 10ms | 58676kb | C++11 | 1.6kb | 2023-02-24 20:11:04 | 2023-02-24 20:11:05 |
Judging History
answer
// what is matter? never mind.
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 2000005
#define inf 0x3f3f3f3f
int n,k,m;
int deg[maxn];
bool e[2005][2005];
vi o[maxn];
vector<pii>res;
bool chk(int x,int y){
vi tmp=o[y];
if(!tmp.size())return 1;
while(tmp.size()){
cout<<"? "<<tmp.size()+1<<" "<<x<<" ";
for(auto t:tmp)cout<<t<<" ";cout<<endl;
int u,v; cin>>u>>v;
if(u==-1){
if(tmp.size()==o[y].size())return 1;
return 0;
}
tmp.erase(find(tmp.begin(),tmp.end(),u^v^x));
for(auto p:tmp)assert(p!=(u^v^x));
res.pb(mkp(u,v));
e[u][v]=e[v][u]=1;
++deg[u],++deg[v];
}
return 0;
}
int p[maxn];
int col[maxn];
bool vis[maxn];
void build(int n){
For(i,1,n)p[i]=i;
sort(p+1,p+n+1,[&](int x,int y){
return deg[x]>deg[y];
});
For(i,1,m) o[i].clear();
m=0;
For(i,1,n){
int u=p[i];
For(j,1,i-1) vis[col[j]]=1;
col[i]=1;
while(vis[col[i]])++col[i];
For(j,1,i-1) vis[col[j]]=0;
m=max(m,col[i]);
o[col[i]].pb(i);
}
}
signed main()
{
cin>>n;
For(i,2,n){
build(i-1);
For(j,1,m) chk(i,j);
}
int mx=*max_element(deg+1,deg+n+1);
assert(m<=mx+1);
cout<<"! "<<res.size()<<endl;
for(auto t:res)cout<<t.fi<<" "<<t.se<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 10ms
memory: 58676kb
input:
3 1 2 1 3 2 3
output:
? 2 2 1 ? 2 3 1 ? 2 3 2 ! 3 1 2 1 3 2 3
result:
ok correct
Test #2:
score: -100
Dangerous Syscalls
input:
10 1 2 1 3 -1 -1 1 4 -1 -1 -1 -1 -1 -1 2 5 -1 -1 4 5 -1 -1 2 6 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 8 4 8 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 9 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 10 4 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
output:
? 2 2 1 ? 2 3 1 ? 2 3 2 ? 2 4 1 ? 2 4 2 ? 2 4 3 ? 2 5 1 ? 2 5 2 ? 2 5 3 ? 2 5 4 ? 2 6 1 ? 2 6 2 ? 2 6 3 ? 2 6 4 ? 2 6 5 ? 2 7 1 ? 2 7 2 ? 2 7 3 ? 2 7 4 ? 2 7 5 ? 2 7 6 ? 2 8 1 ? 2 8 2 ? 2 8 3 ? 2 8 4 ? 2 8 5 ? 2 8 6 ? 2 8 7 ? 2 9 1 ? 2 9 2 ? 2 9 3 ? 2 9 4 ? 2 9 5 ? 2...