QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#32835#1464. Interactive Algorithmdjq_cppWA 328ms3708kbC++1.1kb2022-05-24 21:58:262022-05-24 21:58:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-24 21:58:26]
  • 评测
  • 测评结果：WA
  • 用时：328ms
  • 内存：3708kb
查看
  • [2022-05-24 21:58:26]
  • 提交

answer

//cdw's code, with changed constraints

#include<bits/stdc++.h>
using namespace std;
const int N = 405, K = 8000;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, p[N], deg[N];
bool vis[N][N], has[N];
int main(){
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i = 0;i < n;++ i){p[i] = i; vis[i][i] = true;}
	for(int i = 0, x;i < K;++ i){
		shuffle(p, p + n, rng);
		cout << '?';
		for(int j = 0;j < n;++ j) cout << ' ' << p[j] + 1;
		cout << endl;
		cin >> x;
		if(x == n - 1){
			cout << '!';
			for(int j = 0;j < n;++ j) cout << ' ' << p[j] + 1;
			cout << endl;
			return 0;
		}
		if(!x) for(int j = 0;j < n - 1;++ j)
			vis[p[j]][p[j + 1]] = vis[p[j + 1]][p[j]] = true;
	}
	for(int i = 0;i < n;++ i)
		for(int j = 0;j < n;++ j) deg[i] += !vis[i][j];
	for(p[0] = 0;p[0] < n;++ p[0]) if(deg[p[0]] == 1){
		has[p[0]] = true;
		for(int i = 1;i < n;++ i)
			for(p[i] = 0;p[i] < n;++ p[i])
				if(!vis[p[i - 1]][p[i]] && !has[p[i]]){has[p[i]] = true; break;}
		cout << '!';
		for(int i = 0;i < n;++ i) cout << ' ' << p[i] + 1;
		cout << endl;
		return 0;
	}
}
Source code, Language: C++

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 3632kb

input:

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

output:

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

result:

ok n=5, 150 queries

Test #2:

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

input:

2
1

output:

? 2 1
! 2 1

result:

ok n=2, 1 queries

Test #3:

score: 0
Accepted
time: 3ms
memory: 3596kb

input:

3
2

output:

? 3 2 1
! 3 2 1

result:

ok n=3, 1 queries

Test #4:

score: 0
Accepted
time: 4ms
memory: 3584kb

input:

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

output:

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

result:

ok n=4, 19 queries

Test #5:

score: 0
Accepted
time: 4ms
memory: 3456kb

input:

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

output:

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

result:

ok n=5, 16 queries

Test #6:

score: 0
Accepted
time: 3ms
memory: 3584kb

input:

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

output:

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

result:

ok n=7, 1733 queries

Test #7:

score: 0
Accepted
time: 39ms
memory: 3588kb

input:

10
3
2
4
4
3
3
0
3
0
2
2
0
3
2
2
1
2
0
2
2
4
4
0
0
1
3
1
1
4
1
1
2
2
2
3
1
3
2
2
1
2
2
4
0
3
1
3
2
1
3
4
1
2
2
1
4
2
1
1
1
1
1
4
2
1
3
1
2
2
0
2
2
2
2
1
2
1
2
2
2
0
1
3
0
2
3
1
1
1
3
3
3
2
3
0
3
1
1
3
2
0
2
2
2
3
1
2
2
1
2
2
2
1
2
3
3
0
3
0
3
1
0
4
2
1
2
1
1
4
2
3
2
2
3
2
2
2
3
1
2
0
2
2
1
0
2
4
3
2...

output:

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

result:

ok n=10, 8000 queries

Test #8:

score: 0
Accepted
time: 68ms
memory: 3620kb

input:

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

output:

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

result:

ok n=20, 8000 queries

Test #9:

score: 0
Accepted
time: 100ms
memory: 3704kb

input:

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

output:

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

result:

ok n=30, 8000 queries

Test #10:

score: 0
Accepted
time: 140ms
memory: 3480kb

input:

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

output:

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

result:

ok n=50, 8000 queries

Test #11:

score: 0
Accepted
time: 183ms
memory: 3628kb

input:

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

output:

? 23 31 9 120 39 57 75 41 114 38 86 81 58 102 95 88 118 20 7 66 98 85 111 15 1 13 100 112 101 104 56 35 27 73 74 18 47 119 6 96 50 94 59 33 54 4 77 99 62 8 2 87 117 64 97 72 40 21 123 44 108 83 19 84 3 52 80 34 121 17 90 115 12 110 28 68 122 25 53 48 49 116 103 105 92 61 11 16 51 37 93 60 71 43 89 6...

result:

ok n=123, 8000 queries

Test #12:

score: 0
Accepted
time: 328ms
memory: 3708kb

input:

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

output:

? 62 7 104 71 128 157 154 79 74 19 108 57 55 67 125 36 54 33 8 140 70 164 98 41 94 115 182 118 51 10 86 40 162 52 66 132 37 111 113 169 58 12 83 176 160 134 32 117 173 102 61 123 59 110 11 165 178 27 2 163 177 90 138 80 106 156 21 171 97 148 179 139 16 89 119 133 17 18 105 135 92 131 161 31 126 91 5...

result:

ok n=185, 8000 queries

Test #13:

score: -100
Wrong Answer
time: 293ms
memory: 3628kb

input:

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

output:

? 178 152 148 179 3 258 72 28 25 205 68 269 144 244 121 272 265 139 198 83 22 170 34 45 158 15 207 109 168 128 233 268 183 203 136 84 197 19 125 155 181 142 201 156 164 18 85 175 260 44 131 238 20 115 134 163 223 42 232 218 61 39 193 162 132 186 65 140 87 145 40 234 270 215 246 220 133 80 137 264 20...

result:

wrong output format Unexpected end of file - int32 expected
English 繁體中文 简体中文

Server Time: 2024-12-04 20:04:48 | OpenSource Project