QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#98730#4218. Hidden Graph_yjhRE 0ms0kbC++141.8kb2023-04-19 21:27:392023-04-19 21:27:40

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-19 21:27:40]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-04-19 21:27:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
int n,mx,m,col[2005],d[2005];
bool del[2005],vis[2005];
vector <int> nt[2005];
vector <int> v[2005];
queue <int> q;
int main() {
	cin>>n;
	nt[1].push_back(1);
	mx=1;
	for(int nw=2;nw<=n;nw++) {
		for(int i=1;i<=mx;i++) {
			if(!nt[i].size()) continue;
			int sz=nt[i].size();
			while(sz) {
				cout<<"? "<<sz+1<<' ';
				for(int k:nt[i]) {
					if(!del[k]) cout<<k<<' ';
				}
				cout<<nw<<endl;
				int x,y;
				cin>>x>>y;
				if(x==-1||y==-1) break;
				if(x==nw) swap(x,y);
				v[y].push_back(x);
				v[x].push_back(y);
				m++;
				del[x]=true;
				sz--;
			}
			nt[i].clear();
		}
		mx=n+1;
		for(int i=1;i<=nw;i++) {
			del[i]=false;
			col[i]=0;
//			cout<<i<<' '<<v[i].size()<<'\n';
			mx=min(mx,int(v[i].size())+1);
		    d[i]=v[i].size();
		}
//		cout<<mx<<'\n';
//		if(n==2000) assert(mx<=3);
		for(int i=1;i<=nw;i++) {
			if(d[i]<=mx-1) {
				q.push(i);
				break;
			}
		}
//		cout<<q.front()<<'\n';
		vector <int> tmp;
		while(!q.empty()) {
			int s=q.front();
			q.pop();
			tmp.clear();
			del[s]=true;
		    if(!col[s]) {
		    	for(int to:v[s]) {
		    		if(col[to]) tmp.push_back(col[to]);
				}
				sort(tmp.begin(),tmp.end());
				int nww=1;
				for(int i:tmp) {
					if(nww!=i) break;
					nww++;
				}
//				cout<<"S"<<nww<<'\n';
				col[s]=nww;
				for(int to:v[s]) {
					d[to]--;
					if(d[to]<=mx-1&&!del[to]) q.push(to);
				}
				nt[col[s]].push_back(s);
			}
		}
		for(int i=1;i<=nw;i++) {
			del[i]=false;
			assert(!col[i]);
//			cout<<col[i]<<' ';
		}
//		cout<<'\n';
	}
	cout<<'!'<<' '<<m<<'\n';
	for(int i=1;i<=n;i++) {
		for(int j:v[i]) {
			if(j<i) continue;
			cout<<i<<' '<<j<<'\n';
		}
	}
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

3
1 2

output:

? 2 1 2

result: