QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#338842#4218. Hidden GraphJohnVictor36WA 1ms3924kbC++141.3kb2024-02-26 13:17:152024-02-26 13:17:16

Judging History

This is the latest submission verdict.

  • [2024-02-26 13:17:16]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3924kb
  • [2024-02-26 13:17:15]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
const int mod=998244353;
typedef long long ll;
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second

void add(int &x,int y){x=(x+y>=mod)?(x+y-mod):x+y;}
int qpow(int x,int y){int ret=1;while(y){if(y&1)ret=1ll*ret*x%mod;x=1ll*x*x%mod;y>>=1;}return ret;}
const int N=2005;
int n,k,col[N],cnt,vis[N],tot;
vector<int>f[N],e[N];//f[i] is a independent set

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n;k=1;
	rep(i,1,n)f[1].pb(i),col[i]=1;
	while(1){
		printf("? %d ",f[k].size());
		for(auto x:f[k])printf("%d ",x);puts("");fflush(stdout);
		int i,j;cin>>i>>j;
		if(i==-1&&j==-1){
			for(auto x:f[k])++cnt;k++;
			if(cnt==n)break;
		} 
		else{
			++tot;
			e[i].pb(j);
			e[j].pb(i);
			rep(t,1,n){
				memset(vis,0,sizeof(vis));
				if(col[t]<k)continue;
				for(auto u:e[t])if(u<t){
					vis[col[u]]=1;
				}
				int col=k;while(vis[col])col++;
				::col[t]=col; 
			}
			rep(t,k,n)f[t].clear();
			rep(t,1,n)if(col[t]>=k)f[col[t]].pb(t);
		}
		//printf("Current coloring:\n");
		//rep(i,1,n){
		//	for(auto x:f[i])printf("%d ",x);puts("");
		//}
	}
	printf("! %d\n",tot);
	rep(i,1,n)for(auto x:e[i])if(x<i)printf("%d %d\n",i,x);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3924kb

input:

3
1 3
1 2
-1 -1
2 3
-1 -1
-1 -1

output:

? 3 1 2 3 
? 2 1 2 
? 1 1 
? 2 2 3 
? 1 2 
? 1 3 
! 3
2 1
3 1
3 2

result:

ok correct

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3924kb

input:

10
1 4
2 6
3 7
1 3
1 2
-1 -1
-1 -1

output:

? 10 1 2 3 4 5 6 7 8 9 10 
? 9 1 2 3 5 6 7 8 9 10 
? 8 1 2 3 5 7 8 9 10 
? 7 1 2 3 5 8 9 10 
? 7 1 2 5 7 8 9 10 
? 7 1 5 6 7 8 9 10 
? 3 2 3 4 
! 5
2 1
3 1
4 1
6 2
7 3

result:

wrong answer read 5 edges but expected 12 edges