QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#72173#4926. Where Is the Root?MoQz0 6ms3472kbC++1012b2023-01-14 19:18:092023-01-14 19:18:10

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-14 19:18:10]
  • 评测
  • 测评结果:0
  • 用时:6ms
  • 内存:3472kb
  • [2023-01-14 19:18:09]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
int n;
int d[511],px[511];
bool cmp(int x,int y){
	return (d[x]<d[y]);
}
int main(){
	cin>>n;
	fo(i,1,n-1){
		int x,y;
		cin>>x>>y;
		++d[x],++d[y];
	}
	fo(i,1,n)px[i]=i;
	sort(px+1,px+n+1,cmp);
	int w=1;
	while(w<n&&d[px[w+1]]==1)++w;
	int l=1,r=n;
	char s[10];
	while(l<r&&r>2){
		int mid=(l+r)/2;
		cout<<"? ";
		if(mid<=w){	
			cout<<mid-l+1<<" ";
			fo(i,l,mid)cout<<px[i]<<" ";
			cout<<endl;	
		}
		else{
			cout<<w+max(0,mid-max(l,w+1)+1)<<" ";
			fo(i,1,w)cout<<px[i]<<" ";
			fo(i,max(l,w+1),mid)cout<<px[i]<<" ";
			cout<<endl;
		}
		cout.flush();
		cin>>s;
		if(s[0]=='N')l=mid+1;
		else r=mid;
	}
	if(r==2){
		cout<<"? "<<n-1<<" ";
		fo(i,2,n)cout<<px[i]<<" ";
		cout<<endl;
		cout.flush();
		cin>>s;
		if(s[0]=='N')l=2;
	}
	cout.flush();
	cout<<"! "<<px[l];
	cout.flush();
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 7
Accepted
time: 2ms
memory: 3268kb

input:

7
4 1
1 2
4 3
3 5
3 6
4 7
NO
NO

output:

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

result:

ok OK

Test #2:

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

input:

9
5 9
8 6
2 8
1 8
3 6
6 7
1 4
4 5
YES
YES
YES
YES

output:

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

result:

ok OK

Test #3:

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

input:

9
6 8
2 5
5 1
4 3
5 9
6 3
6 1
7 5
YES
NO
YES

output:

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

result:

ok OK

Test #4:

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

input:

9
1 8
9 4
7 8
5 7
3 9
2 5
9 1
4 6
YES
YES
NO

output:

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

result:

ok OK

Test #5:

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

input:

9
7 1
8 4
2 8
5 2
2 3
1 2
1 9
9 6
YES
YES
YES
YES

output:

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

result:

ok OK

Test #6:

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

input:

9
1 5
9 8
3 9
7 9
9 1
6 9
4 6
2 3
NO
NO
NO

output:

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

result:

ok OK

Test #7:

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

input:

9
5 2
6 3
1 9
2 6
7 4
6 8
7 5
4 9
NO
YES
YES

output:

? 5 1 3 8 2 4 
? 5 1 3 8 5 7 
? 4 1 3 8 5 
! 5

result:

ok OK

Test #8:

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

input:

9
7 9
7 8
4 2
5 6
9 1
2 8
3 5
4 5
NO
YES
YES

output:

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

result:

ok OK

Test #9:

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

input:

9
3 2
8 9
8 5
5 2
4 6
9 1
6 7
3 6
NO
NO
YES

output:

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

result:

ok OK

Test #10:

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

input:

9
5 6
3 9
5 9
3 4
2 4
7 6
4 8
7 1
YES
NO
YES

output:

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

result:

ok OK

Test #11:

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

input:

9
8 3
7 9
4 3
9 4
5 2
9 6
2 1
8 5
YES
NO
NO

output:

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

result:

ok OK

Test #12:

score: -7
Wrong Answer
time: 2ms
memory: 3408kb

input:

9
8 1
1 5
7 1
1 3
1 4
6 1
1 9
2 1
NO
NO
YES

output:

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

result:

wrong output format Unexpected end of file - int32 expected

Subtask #2:

score: 0
Wrong Answer

Test #24:

score: 10
Accepted
time: 2ms
memory: 3460kb

input:

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

output:

? 15 2 28 25 24 23 21 20 19 17 16 14 12 11 10 9 
? 8 2 28 25 24 23 21 20 19 
? 4 2 28 25 24 
? 2 23 21 
? 1 23 
! 23

result:

ok OK

Test #25:

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

input:

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

output:

? 15 21 18 17 16 14 13 20 11 9 8 22 24 25 4 27 
? 8 21 18 17 16 14 13 20 11 
? 4 21 18 17 16 
? 2 14 13 
? 1 14 
! 14

result:

ok OK

Test #26:

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

input:

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

output:

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

result:

ok OK

Test #27:

score: -10
Wrong Answer
time: 3ms
memory: 3472kb

input:

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

output:

? 15 24 19 20 15 14 13 21 22 10 25 7 26 27 4 28 
? 8 24 19 20 15 14 13 21 22 
? 4 10 25 7 26 
? 2 10 25 
? 1 7 
! 7

result:

wrong output format Unexpected end of file - int32 expected

Subtask #3:

score: 0
Wrong Answer

Test #54:

score: 83
Accepted
time: 5ms
memory: 3268kb

input:

500
419 133
44 225
391 269
419 461
293 347
108 31
110 363
423 257
321 155
498 87
180 492
251 5
357 30
341 172
275 109
372 446
286 336
208 339
162 320
138 103
129 219
62 141
359 286
130 238
470 460
418 48
210 358
429 13
323 143
382 415
406 394
309 175
325 170
128 108
6 113
363 17
470 457
7 224
288 48...

output:

? 250 283 299 298 296 294 292 290 289 287 285 284 300 282 281 280 279 277 276 273 270 268 318 332 331 330 328 327 326 324 323 322 320 264 317 316 313 312 310 307 305 304 303 192 210 209 208 205 204 201 199 198 197 196 211 191 189 181 177 174 173 171 169 168 235 260 257 256 254 252 250 246 245 242 33...

result:

ok OK

Test #55:

score: 83
Accepted
time: 4ms
memory: 3308kb

input:

500
188 321
193 4
334 269
259 66
121 396
73 153
332 477
263 67
178 262
185 377
175 53
462 245
390 337
387 200
445 92
387 159
135 263
323 312
143 374
252 47
375 382
303 345
345 283
150 1
66 289
462 82
317 201
169 423
154 193
486 251
368 305
357 375
107 443
437 348
64 55
408 465
315 469
186 328
197 39...

output:

? 250 237 441 250 249 248 247 246 442 444 446 252 236 235 233 451 227 454 223 222 267 278 276 275 273 272 271 270 269 455 264 439 262 261 260 258 257 253 168 186 184 183 181 180 177 175 173 171 189 167 469 163 471 157 155 154 149 202 219 218 458 215 212 209 460 203 280 201 199 197 195 194 463 191 19...

result:

ok OK

Test #56:

score: 83
Accepted
time: 6ms
memory: 3268kb

input:

500
423 179
253 294
3 58
24 345
129 8
428 443
349 246
15 286
367 428
272 290
294 230
144 239
403 270
354 110
17 157
441 227
216 226
220 211
199 353
397 445
204 269
234 452
283 355
58 375
500 400
284 11
388 235
385 21
53 124
77 290
395 235
71 351
300 26
109 326
462 215
87 405
116 196
430 136
481 390
...

output:

? 250 278 296 295 293 288 287 286 285 283 281 280 297 275 271 270 268 266 263 262 260 259 312 326 325 322 320 319 318 317 315 314 313 258 311 310 309 308 306 304 302 300 298 184 206 204 203 198 194 190 189 187 186 185 208 181 180 179 178 175 173 172 170 169 233 257 250 249 247 246 244 243 241 236 32...

result:

ok OK

Test #57:

score: 0
Wrong Answer
time: 2ms
memory: 3264kb

input:

500
246 390
321 345
385 319
393 475
36 188
453 174
35 111
420 55
411 304
78 250
483 12
241 37
295 498
348 52
105 329
321 255
222 272
457 247
262 189
239 31
114 489
45 321
269 380
493 340
287 128
248 33
201 388
12 379
231 65
94 241
85 43
262 391
154 156
92 140
58 117
44 166
284 480
290 44
157 393
32 ...

output:

? 250 285 300 298 297 295 294 292 290 289 288 286 301 283 282 281 276 275 273 270 268 266 265 323 337 334 332 331 329 328 327 326 325 324 263 320 318 317 312 311 308 307 305 304 194 215 213 212 210 206 203 202 199 198 197 219 191 190 187 186 185 182 180 178 176 175 243 260 259 257 256 255 253 252 25...

result:

wrong output format Unexpected end of file - int32 expected