QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#411111#1464. Interactive Algorithmjqdai0724ML 62ms3612kbC++171.7kb2024-05-14 22:59:052024-05-14 22:59:05

Judging History

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

  • [2024-05-14 22:59:05]
  • 评测
  • 测评结果：ML
  • 用时：62ms
  • 内存：3612kb
查看
  • [2024-05-14 22:59:05]
  • 提交

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;
	For(i,1,n)For(j,i+1,n)e[i][j]=e[j][i]=1;
	For(_,1,8000){
		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]]=e[p[i+1]][p[i]]=0,--deg[p[i]],--deg[p[i+1]];
//			bool ok=1;
//			For(i,1,n)
//				if(deg[i]>2){ok=0;break;}
////			For(i,1,n)cout<<deg[i]<<" ";puts("");
////			For(i,1,n)For(j,1,n)cout<<e[i][j]<<" \n"[j==n];
//			if(ok){
//				cout<<"! ";
//				For(i,1,n)if(deg[i]==1)dfs(i,0),cout<<endl,exit(0);
//				assert(0);
//			}
		}
	}
	cout<<"! ";
	For(i,1,n)if(deg[i]==1)dfs(i,0),exit(0);
	return 0;
}
/*
1 2 3 4

*/
源文件, 语言: C++17

詳細信息

Test #1:

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

input:

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

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 
? 3 4 2 5 1 
! 3 4 2 5 1

result:

ok n=5, 20 queries

Test #2:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

2
1

output:

? 2 1 
! 2 1

result:

ok n=2, 1 queries

Test #3:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

3
1
2

output:

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

result:

ok n=3, 2 queries

Test #4:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

4
3

output:

? 3 1 4 2 
! 3 1 4 2

result:

ok n=4, 1 queries

Test #5:

score: 0
Accepted
time: 1ms
memory: 3556kb

input:

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

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 
? 3 4 2 5 1 
? 5 4 3 1 2 
? 2 4 1 3 5 
? 2 4 1 5 3 
?...

result:

ok n=5, 114 queries

Test #6:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

7
1
0
1
1
2
2
1
1
2
3
4
0
2
4
2
2
3
0
3
1
2
1
0
2
3
2
3
2
0
3
2
3
2
1
1
1
2
4
2
2
2
2
2
2
0
1
1
1
4
2
1
3
1
2
3
1
2
2
2
1
2
3
0
0
2
2
2
3
2
0
2
3
1
3
2
1
0
4
2
2
2
4
2
4
2
3
0
1
0
1
1
2
3
1
2
1
4
2
0
1
2
2
2
2
1
1
4
0
2
1
2
3
2
2
2
1
1
2
3
3
1
3
1
1
0
1
1
2
3
3
1
0
2
1
3
1
3
3
1
4
0
4
2
3
0
1
3
1
0
...

output:

? 4 1 6 3 5 2 7 
? 1 6 3 4 5 7 2 
? 4 3 2 6 1 7 5 
? 7 6 3 2 1 5 4 
? 1 5 6 2 7 3 4 
? 2 1 3 5 6 7 4 
? 2 7 6 5 1 4 3 
? 3 4 2 5 6 7 1 
? 7 3 4 6 5 2 1 
? 2 6 5 3 1 7 4 
? 1 5 2 3 6 4 7 
? 2 1 6 7 3 5 4 
? 7 2 6 5 1 4 3 
? 1 3 5 2 6 7 4 
? 6 3 2 5 4 7 1 
? 6 4 2 1 5 7 3 
? 2 6 3 5 1 4 7 
? 4 5 3 2 1...

result:

ok n=7, 1018 queries

Test #7:

score: 0
Accepted
time: 11ms
memory: 3528kb

input:

10
2
1
1
1
4
3
2
2
2
1
2
1
3
1
5
2
1
3
0
0
0
2
1
2
1
1
2
1
4
3
1
2
0
2
2
2
0
2
3
1
5
2
1
1
1
1
1
2
1
3
2
3
1
1
6
3
2
2
0
4
1
1
6
3
1
0
2
2
2
3
0
0
0
2
1
2
2
1
3
3
0
0
0
2
1
2
3
2
2
1
2
1
2
3
2
1
0
2
2
3
2
0
2
3
1
3
1
2
1
3
1
0
2
0
3
1
3
2
2
3
1
1
2
0
0
3
1
1
1
1
0
2
1
4
1
1
1
2
3
2
5
3
1
2
2
1
1
1
1...

output:

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

result:

ok n=10, 8000 queries

Test #8:

score: 0
Accepted
time: 21ms
memory: 3472kb

input:

20
3
2
1
1
3
3
0
5
2
1
1
2
2
2
3
2
3
3
2
1
4
2
4
1
1
2
0
2
2
1
2
1
2
5
4
1
3
4
2
3
2
3
1
2
1
3
4
1
0
2
5
3
3
2
3
2
0
2
3
1
1
2
4
2
0
2
1
0
2
1
3
5
2
2
1
2
0
0
3
2
2
3
1
2
1
2
3
5
0
1
4
1
0
1
3
3
5
2
2
0
4
2
2
2
1
1
1
2
2
0
3
2
1
1
2
3
2
3
3
0
2
2
1
0
0
2
1
2
0
5
1
4
3
1
3
2
1
5
1
0
0
4
3
1
1
2
3
2
2...

output:

? 3 7 16 2 18 20 12 1 8 14 11 10 6 9 13 19 15 4 17 5 
? 16 6 8 11 3 12 19 13 1 14 10 15 4 18 7 9 17 2 20 5 
? 6 5 20 3 16 2 17 11 19 13 10 1 15 7 18 4 8 12 14 9 
? 9 3 14 11 7 19 10 6 2 5 8 4 1 12 20 16 13 15 18 17 
? 4 3 13 5 1 6 9 19 2 10 16 15 7 20 11 8 12 18 14 17 
? 10 20 2 8 4 14 16 15 6 9 11 ...

result:

ok n=20, 8000 queries

Test #9:

score: 0
Accepted
time: 10ms
memory: 3568kb

input:

30
0
2
1
1
1
1
3
1
7
4
3
0
0
1
5
3
2
3
3
3
2
3
2
2
2
1
6
3
0
0
2
2
3
3
3
2
1
0
3
1
4
1
1
2
2
1
2
3
1
1
2
1
0
1
1
2
0
3
2
2
1
0
3
2
3
0
6
4
3
0
0
0
2
1
2
1
3
3
3
2
1
2
1
3
0
1
3
3
4
2
1
0
1
3
2
1
2
3
0
1
2
3
3
1
2
3
2
3
1
2
3
1
1
2
1
2
1
1
2
3
3
0
2
4
2
2
3
3
3
2
4
1
3
3
0
1
2
2
3
1
0
3
2
2
1
2
1
2
1...

output:

? 3 7 16 23 18 24 12 22 8 29 28 10 6 9 13 19 30 25 17 5 27 1 2 20 26 4 11 21 14 15 
? 29 23 17 14 12 15 6 1 8 11 3 13 20 5 28 22 10 30 24 27 16 4 25 19 7 26 9 21 2 18 
? 27 14 24 1 25 8 21 29 15 26 10 16 19 30 9 12 11 20 28 6 22 5 4 13 7 23 2 3 17 18 
? 23 21 11 8 28 6 19 9 17 1 25 10 22 29 5 27 12 ...

result:

ok n=30, 8000 queries

Test #10:

score: 0
Accepted
time: 12ms
memory: 3592kb

input:

50
2
2
2
4
4
6
3
0
4
1
4
4
1
2
5
0
4
2
2
3
2
2
4
0
2
0
3
2
1
3
2
0
4
3
1
2
2
3
1
1
1
2
1
4
1
0
1
1
1
1
2
1
3
3
1
1
0
1
2
4
3
4
3
4
2
1
0
2
0
2
1
2
2
3
1
2
3
3
3
3
2
5
0
3
2
1
1
3
1
2
3
3
4
4
2
4
3
0
0
2
3
2
1
3
4
3
1
3
1
2
2
3
1
4
0
5
1
2
0
2
2
3
2
0
1
4
3
1
3
4
1
2
3
5
2
3
1
1
1
1
1
4
3
3
3
1
3
3
3...

output:

? 32 7 44 33 18 24 49 36 47 42 28 31 41 9 13 19 46 35 17 5 27 1 43 20 26 37 11 21 14 15 10 3 23 4 40 45 34 30 25 39 6 29 2 48 22 38 8 50 12 16 
? 47 21 15 14 45 32 23 8 44 42 19 50 37 2 13 41 4 11 16 30 49 29 18 33 1 27 28 46 9 35 20 10 24 3 40 48 25 6 31 17 22 38 7 26 34 36 12 39 43 5 
? 42 25 27 3...

result:

ok n=50, 8000 queries

Test #11:

score: 0
Accepted
time: 62ms
memory: 3612kb

input:

123
1
2
1
2
1
3
2
0
4
2
1
3
1
2
4
1
2
2
2
1
8
0
0
2
2
2
4
2
0
0
6
3
3
2
0
1
4
2
3
2
2
1
2
0
2
2
0
3
2
5
2
2
3
5
3
3
2
2
1
0
3
3
0
2
0
4
3
0
2
3
3
3
2
3
4
2
2
2
0
1
2
3
1
1
5
3
7
1
5
2
6
2
3
3
1
0
1
1
0
4
3
4
1
1
5
1
7
1
2
0
1
1
1
1
3
3
0
0
1
1
4
0
3
2
0
2
0
5
1
3
1
2
1
2
2
4
3
1
1
6
0
4
2
3
2
1
3
3
...

output:

? 9 21 19 34 68 17 60 50 80 48 99 32 108 76 55 98 84 36 93 95 1 79 65 103 110 45 38 67 59 6 94 12 7 29 2 123 61 89 11 27 102 81 105 82 23 85 88 52 104 78 106 77 31 25 8 83 49 75 24 13 113 20 35 57 66 101 91 112 71 43 40 87 5 4 28 15 30 47 116 54 72 70 118 90 107 62 33 111 121 86 73 122 26 41 100 10 ...

result:

ok n=123, 8000 queries

Test #12:

score: -100
Memory Limit Exceeded

input:

185
4
0
1
0
1
1
4
2
1
2
6
3
3
0
1
6
1
1
1
2
5
1
1
1
2
2
1
1
1
1
1
1
1
0
3
0
4
2
5
3
2
3
1
1
2
5
6
2
2
2
4
4
1
0
1
6
4
2
2
4
0
5
3
2
2
1
3
1
3
0
1
0
6
5
2
0
1
1
2
2
1
1
1
2
3
2
0
0
1
2
3
1
2
2
2
1
1
0
2
0
3
3
1
2
5
4
3
1
1
3
3
2
1
2
0
4
1
1
1
4
2
3
2
1
2
2
1
2
3
3
3
1
1
2
1
1
1
1
2
1
2
1
3
0
0
0
2
3
...

output:

? 9 153 162 34 68 138 60 50 80 48 169 32 108 172 156 98 84 36 154 141 1 79 65 103 110 182 38 67 157 149 94 143 7 29 2 123 61 148 180 27 102 81 105 82 23 85 88 166 104 78 124 77 31 168 8 83 134 175 161 13 113 20 35 57 174 144 91 112 176 140 128 87 5 4 28 170 181 47 116 54 179 70 118 90 155 164 145 11...

result:
English 繁體中文 简体中文

伺服器時間: 2024-12-05 05:27:59 | 開源專案