QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#32837#1464. Interactive Algorithmdjq_cppWA 719ms3716kbC++1.1kb2022-05-24 22:16:212022-05-24 22:16:21

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 22:16:21]
  • 评测
  • 测评结果：WA
  • 用时：719ms
  • 内存：3716kb
查看
  • [2022-05-24 22:16:21]
  • 提交

answer

//cdw's code, with changed constraints

#include<bits/stdc++.h>
using namespace std;
const int N = 405, K = 15000;
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: 7ms
memory: 3488kb

input:

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

output:

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

result:

ok n=5, 51 queries

Test #2:

score: 0
Accepted
time: 2ms
memory: 3552kb

input:

2
1

output:

? 2 1
! 2 1

result:

ok n=2, 1 queries

Test #3:

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

input:

3
1
1
1
1
2

output:

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

result:

ok n=3, 5 queries

Test #4:

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

input:

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

output:

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

result:

ok n=4, 12 queries

Test #5:

score: 0
Accepted
time: 5ms
memory: 3572kb

input:

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

output:

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

result:

ok n=5, 23 queries

Test #6:

score: 0
Accepted
time: 20ms
memory: 3640kb

input:

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

output:

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

result:

ok n=7, 3655 queries

Test #7:

score: 0
Accepted
time: 172ms
memory: 3580kb

input:

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

output:

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

result:

ok n=10, 15000 queries

Test #8:

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

input:

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

output:

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

result:

ok n=20, 15000 queries

Test #9:

score: 0
Accepted
time: 219ms
memory: 3668kb

input:

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

output:

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

result:

ok n=30, 15000 queries

Test #10:

score: 0
Accepted
time: 201ms
memory: 3532kb

input:

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

output:

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

result:

ok n=50, 15000 queries

Test #11:

score: 0
Accepted
time: 386ms
memory: 3624kb

input:

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

output:

? 19 39 45 21 24 78 36 79 40 6 107 75 82 77 119 72 123 87 27 41 93 46 84 110 20 60 14 94 51 56 90 43 97 17 114 10 69 118 54 3 28 120 11 112 115 88 47 70 101 117 55 67 44 48 57 111 99 105 52 15 86 16 9 31 89 29 49 4 108 116 58 80 22 32 81 26 104 74 2 8 35 62 66 98 71 95 85 64 1 7 83 73 38 122 59 68 1...

result:

ok n=123, 15000 queries

Test #12:

score: 0
Accepted
time: 445ms
memory: 3652kb

input:

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

output:

? 181 176 104 61 140 78 68 42 155 74 80 164 179 91 66 101 12 2 38 145 88 46 157 70 106 172 170 122 128 110 24 67 72 79 102 30 49 43 160 45 48 54 6 167 162 7 166 159 169 92 35 9 135 52 40 47 8 133 26 73 69 53 105 77 125 147 22 171 1 63 96 94 144 16 51 111 130 116 108 58 20 107 32 19 117 71 173 139 14...

result:

ok n=185, 15000 queries

Test #13:

score: 0
Accepted
time: 586ms
memory: 3688kb

input:

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

output:

? 112 151 58 5 81 265 153 261 185 131 157 177 11 60 250 146 128 187 69 178 78 179 3 44 18 199 33 19 263 66 73 125 176 15 40 105 195 103 144 150 75 209 266 274 264 1 161 98 100 201 8 240 139 93 134 249 239 181 119 14 247 221 46 218 163 10 49 189 143 137 25 168 17 52 190 111 162 188 147 220 159 36 236...

result:

ok n=277, 15000 queries

Test #14:

score: 0
Accepted
time: 573ms
memory: 3688kb

input:

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

output:

? 203 236 130 273 258 46 209 181 178 184 117 218 5 260 29 109 32 56 147 85 114 151 215 102 242 297 198 45 82 26 222 143 299 272 228 142 125 249 173 52 89 9 164 144 13 214 122 185 63 15 291 212 284 75 261 134 148 187 129 44 131 161 167 51 227 11 269 226 179 91 112 41 87 158 280 111 253 192 254 278 14...

result:

ok n=300, 15000 queries

Test #15:

score: -100
Wrong Answer
time: 719ms
memory: 3716kb

input:

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

output:

? 51 32 302 33 65 235 186 246 178 134 303 278 121 225 194 240 184 114 344 262 314 31 143 305 265 110 135 154 316 329 289 249 67 259 211 332 2 223 151 47 79 323 117 21 92 130 138 54 196 337 215 95 9 133 321 69 13 46 166 105 112 22 319 280 272 35 132 104 266 213 245 288 198 20 308 118 260 276 285 165 ...

result:

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

Server Time: 2024-12-04 20:23:17 | OpenSource Project