QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#339075#4218. Hidden GraphYMH_fourteenRE 0ms0kbC++141.8kb2024-02-26 18:28:182024-02-26 18:28:18

Judging History

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

  • [2024-02-26 18:28:18]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-02-26 18:28:18]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "templates/debug.h"
#else
#define dbg(...) (void)0
#define msg(...) (void)0
#endif
#define ll long long
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define ALL(Name) Name.begin(),Name.end()
#define PII pair<int,int>
#define VI vector<int>
#define fi first
#define se second



int main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr);
//	int _;cin>>_;while(_--)

	int n;
	cin>>n;
	vector<VI>g;
	g.PB(VI());
	auto work=[&](int x,VI &ord)->bool
	{
		ord.clear();
		int _n=g.size();
		VI ds(_n);
		for(int i=0;i<_n;i++)
			ds[i]=g[i].size();
		for(int i=0;i<_n;i++)
		{
			int id=-1;
			for(int j=0;j<_n;j++)
				if(ds[j]<=x){id=j;break;}
			if(!~id)return 0;
			ord.PB(id);
			ds[id]=INT_MAX;
			for(int j:g[id])ds[j]--;
		}
		return 1;
	};

	for(int i=1;i<n;i++)
	{
		VI ord;
		int l=1,r=i;
		while(l<=r)
		{
			int mid=l+r>>1;
			work(mid-1,ord)?r=mid-1:l=mid+1;
		}
		assert(work(l-1,ord));
		reverse(ALL(ord));
		VI col(i);col.assign(i,-1);
		for(int j:ord)
		{
			set<int>nex;
			for(int k=0;k<=l;k++)nex.insert(k);
			for(int k:g[j])nex.erase(col[k]);
			col[j]=*nex.begin();
		}
		g.PB(VI());
		for(int j=0;j<=l;j++)
		{
			set<int>st;
			for(int k=0;k<i;k++)
				if(col[k]==j)st.insert(k);
			while(!st.empty())
			{
				cout<<"! "<<st.size()+1<<" ";
				for(int j:st)cout<<j+1<<" ";
				cout<<i+1<<endl;
				int x,y;
				cin>>x>>y;
				if(~x)
				{
					--x,--y;
					if(x>y)swap(x,y);
					g[x].PB(y),g[y].PB(x);
					st.erase(x);
				}
				else break;
			}
		}
	}
	int sum=0;
	for(auto i:g)sum+=i.size();
	cout<<"! "<<sum/2<<endl;
	for(int i=0;i<n;i++)
		for(int j:g[i])
			if(i<j)cout<<i+1<<" "<<j+1<<endl;

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

3

output:

! 2 1 2

result: