QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#121287#1464. Interactive AlgorithmCrysflyML 0ms0kbC++171.5kb2023-07-07 20:56:552023-07-07 20:56:58

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-07 20:56:58]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2023-07-07 20:56:55]
  • 提交

answer

// what is matter? never mind. 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#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
#define ull unsigned 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 200005
#define inf 0x3f3f3f3f

int n,p[maxn];
mt19937_64 rnd(114514);

bool e[405][405];
int deg[405];

void dfs(int u,int pa){
	cout<<u<<" ";
	For(v,1,n)
		if(v!=pa && e[u][v])dfs(v,u);
}

signed main()
{
	cin>>n;
	For(i,1,n)p[i]=i;
	For(i,1,n)deg[i]=n-1;
	memset(e,1,sizeof e);
	For(_,1,25000){
		shuffle(p+1,p+n+1,rnd);
		cout<<"? ";
		For(i,1,n)cout<<p[i]<<" ";cout<<endl;
		int x;cin>>x;
		if(x==n-1){
			cout<<"! ";
			For(i,1,n)cout<<p[i]<<" ";cout<<endl;
			exit(0);
		}
		if(x==0){
			For(i,1,n-1)
				if(e[p[i]][p[i+1]])
					e[p[i]][p[i+1]]=0,--deg[p[i]],--deg[p[i+1]];
			bool ok=1;
			For(i,1,n)
				if(deg[i]>2){ok=0;break;}
			if(ok){
				cout<<"! ";
				For(i,1,n)if(deg[i]==1)dfs(i,0);
				cout<<endl;
				exit(0);
			}
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Memory Limit Exceeded

input:

5
0
1
2
2
1
3
2
2
1
3
1
1
1
2
2
2
2
3
0

output:

? 4 1 2 3 5 
? 5 3 2 4 1 
? 5 2 3 4 1 
? 4 3 1 2 5 
? 4 5 1 2 3 
? 2 4 3 5 1 
? 1 3 4 5 2 
? 3 5 2 4 1 
? 2 4 5 3 1 
? 2 5 1 3 4 
? 4 1 3 2 5 
? 2 3 1 5 4 
? 1 2 3 4 5 
? 3 1 5 4 2 
? 4 3 2 1 5 
? 5 2 4 1 3 
? 1 3 4 5 2 
? 4 2 5 1 3 
? 1 4 5 3 2 
! 1 1 3 3 1 1 3 3 1 1 3 3 1 1 3 3 1 1 3 3 1 1 3 3 1 1...

result: