QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#72173 | #4926. Where Is the Root? | MoQz | 0 | 6ms | 3472kb | C++ | 1012b | 2023-01-14 19:18:09 | 2023-01-14 19:18:10 |
Judging History
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