QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #750492 | #8363. interactive | xcc_szy0905 | 10 | 197ms | 9172kb | C++14 | 1.4kb | 2024-11-15 14:44:42 | 2024-11-15 14:44:43 |
Judging History
answer
#include<bits/stdc++.h>
#include "interactive.h"
using namespace std;
const int kmaxn=505;
vector<int>an;
int ip[kmaxn],now,dm[kmaxn][kmaxn],cnt[kmaxn][kmaxn];
double ppc[kmaxn][kmaxn];
int n;
bool pd[kmaxn];
bool cmp(int x,int y){
return (ppc[now][x]/cnt[now][x])>(ppc[now][y]/cnt[now][y]);
}
void dfs(int x,int f){
an.push_back(x);
pd[x]=1;now=x;for(int i=1;i<=n;i++)ip[i]=i;
sort(ip+1,ip+1+n,cmp);
for(int I=1;I<=n;I++){
int i=ip[I];
if(dm[x][i]&&i!=f&&i!=x&&!pd[i]){
dfs(i,x);
}
}
}
int cont(vector<int>x){
int cp=0;
for(int i=0;i<x.size()-1;i++){
if(dm[x[i]][x[i+1]]==0)cp++;
}
return cp;
}
bool cmd(vector<int>x,vector<int>y){
return cont(x)>cont(y);
}
std::vector<int> solve(int N){
// freopen("Md.out","w",stdout);
n=N;
srand(time(0));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dm[i][j]=1;
}
}
vector<int>pr,O[10];
for(int i=1;i<=n;i++){
pr.push_back(i);
}
for(int I=1;I<16000;I++){
random_shuffle(pr.begin(),pr.end());
int op=query(pr);
if(n==3){
if(op==2){
return pr;
}
}
for(int i=0;i<n-1;i++){
int u=pr[i],v=pr[i+1];
cnt[u][v]++,cnt[v][u]++;
ppc[u][v]+=op;ppc[v][u]+=op;
dm[u][v]=min(dm[u][v],op);
dm[v][u]=min(dm[v][u],op);
}
}
int pq=0;
for(int i=1;i<=n;i++){
int sz=0;
for(int j=1;j<=n;j++){
if(i!=j&&dm[i][j])sz++;
}
if(sz>2)pq++;
if(sz==1){dfs(i,0);return an;}
}
return an;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 3884kb
input:
1 3 3 1 2
output:
1 26286 7113
result:
points 1.0
Test #2:
score: 10
Accepted
time: 7ms
memory: 6120kb
input:
1 30 6 28 10 9 13 4 7 1 21 15 20 27 19 5 17 2 22 12 29 23 14 30 18 3 11 24 26 16 8 25
output:
15999 120397645 537621159
result:
points 1.0
Test #3:
score: 10
Accepted
time: 3ms
memory: 8308kb
input:
1 27 24 17 15 3 13 9 6 16 14 22 7 19 25 12 1 26 23 27 10 21 8 5 18 11 20 4 2
output:
15999 120397645 966160455
result:
points 1.0
Test #4:
score: 10
Accepted
time: 7ms
memory: 6208kb
input:
1 29 24 8 7 14 19 20 4 6 1 12 18 2 10 3 23 13 26 11 22 27 9 17 16 5 21 29 25 15 28
output:
15999 120397645 646167394
result:
points 1.0
Test #5:
score: 10
Accepted
time: 7ms
memory: 6384kb
input:
1 30 9 22 10 27 8 5 23 21 2 25 6 13 30 19 17 20 4 14 29 28 24 15 11 7 12 18 26 16 3 1
output:
15999 120397645 904341262
result:
points 1.0
Test #6:
score: 10
Accepted
time: 3ms
memory: 7984kb
input:
1 27 8 6 11 20 24 7 9 25 13 19 2 3 23 15 16 4 22 21 10 18 12 27 14 5 1 17 26
output:
15999 120397645 173992498
result:
points 1.0
Test #7:
score: 10
Accepted
time: 7ms
memory: 8260kb
input:
1 27 2 5 25 13 11 12 23 24 6 18 19 21 15 17 7 10 16 20 22 27 3 4 8 14 26 1 9
output:
15999 120397645 772894146
result:
points 1.0
Test #8:
score: 10
Accepted
time: 3ms
memory: 7980kb
input:
1 27 13 11 10 27 20 23 3 25 12 24 6 2 19 9 7 17 1 5 8 26 14 16 21 15 22 4 18
output:
15999 120397645 181323461
result:
points 1.0
Test #9:
score: 10
Accepted
time: 7ms
memory: 8320kb
input:
1 27 3 15 12 14 18 27 23 6 20 26 21 5 13 19 10 9 11 17 16 4 25 7 24 2 22 1 8
output:
15999 120397645 480249695
result:
points 1.0
Test #10:
score: 10
Accepted
time: 7ms
memory: 6144kb
input:
1 29 23 7 4 10 9 16 1 14 3 17 13 19 15 8 5 22 24 29 11 12 18 25 21 2 28 26 27 20 6
output:
15999 120397645 31142540
result:
points 1.0
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 90
Accepted
time: 4ms
memory: 8052kb
input:
1 27 17 16 3 20 27 5 2 13 24 21 25 23 19 9 7 4 22 12 26 15 14 11 1 18 6 10 8
output:
15999 120397645 558749364
result:
points 1.0
Test #12:
score: 90
Accepted
time: 3ms
memory: 6140kb
input:
1 29 19 13 20 22 26 1 23 24 3 14 8 25 29 17 10 9 15 11 18 4 2 28 21 7 6 12 16 27 5
output:
15999 120397645 145445666
result:
points 1.0
Test #13:
score: 90
Accepted
time: 7ms
memory: 6108kb
input:
1 28 16 7 19 9 23 12 20 26 4 10 15 8 21 5 1 22 27 2 18 24 28 6 3 14 13 17 25 11
output:
15999 120397645 877668399
result:
points 1.0
Test #14:
score: 90
Accepted
time: 3ms
memory: 4164kb
input:
1 30 13 4 29 25 16 14 6 15 19 28 7 20 3 23 12 17 8 22 1 24 9 30 21 18 2 26 27 10 11 5
output:
15999 120397645 737974315
result:
points 1.0
Test #15:
score: 90
Accepted
time: 3ms
memory: 8020kb
input:
1 27 18 25 15 20 23 14 4 16 27 6 2 12 21 19 17 26 9 8 10 11 3 7 13 22 24 5 1
output:
15999 120397645 590934171
result:
points 1.0
Test #16:
score: 66.003
Acceptable Answer
time: 184ms
memory: 8804kb
input:
2 494 364 164 445 359 288 412 15 377 91 481 14 3 357 358 269 136 336 106 392 200 50 388 33 338 114 11 266 186 170 239 494 196 395 68 36 423 378 218 342 275 67 240 120 86 134 356 190 323 123 339 187 30 270 430 292 121 372 404 94 143 454 309 461 344 141 480 474 248 199 42 150 260 369 483 493 124 396 4...
output:
15999 120397645 998930322
result:
points 0.73336666670
Test #17:
score: 66.003
Acceptable Answer
time: 194ms
memory: 8844kb
input:
2 500 468 70 339 65 443 143 75 123 220 163 390 484 489 139 392 147 183 132 202 14 19 380 310 259 179 482 85 36 232 419 285 378 137 274 376 23 321 263 217 485 387 466 94 104 164 57 185 359 42 211 40 206 418 184 458 173 441 291 11 366 428 384 223 190 374 34 275 210 171 226 408 168 88 494 204 66 481 10...
output:
15999 120397645 110390244
result:
points 0.73336666670
Test #18:
score: 66.003
Acceptable Answer
time: 188ms
memory: 8848kb
input:
2 500 217 120 312 323 22 113 331 295 315 66 434 181 381 421 154 253 226 100 152 490 389 261 244 249 165 500 4 426 23 487 356 466 364 436 2 374 486 494 420 14 344 34 26 475 279 96 457 493 185 147 227 41 180 61 472 102 76 131 141 164 324 204 403 298 283 284 19 132 258 355 499 183 108 483 348 172 134 2...
output:
15999 120397645 177306504
result:
points 0.73336666670
Test #19:
score: 66.003
Acceptable Answer
time: 187ms
memory: 8788kb
input:
2 496 483 115 328 488 147 188 287 16 251 1 30 170 224 187 15 156 61 366 232 472 474 92 10 457 228 28 109 261 229 480 7 84 180 65 313 239 380 359 464 339 471 484 356 485 435 352 220 454 430 113 39 494 311 149 396 81 346 226 145 345 354 402 298 433 99 208 289 424 79 97 300 93 186 425 470 383 183 165 2...
output:
15999 120397645 595257989
result:
points 0.73336666670
Test #20:
score: 66.003
Acceptable Answer
time: 186ms
memory: 8844kb
input:
2 498 275 455 229 213 132 452 185 346 279 90 113 30 162 148 69 1 154 11 310 66 435 153 86 52 467 477 201 12 121 238 84 67 5 436 401 496 340 6 463 411 343 360 88 473 57 396 14 106 144 22 98 472 422 149 25 168 59 363 165 323 112 317 127 383 46 68 212 138 389 330 4 361 200 203 492 50 263 355 242 33 267...
output:
15999 120397645 79267961
result:
points 0.73336666670
Test #21:
score: 66.003
Acceptable Answer
time: 189ms
memory: 9172kb
input:
2 499 218 441 27 245 323 157 414 380 126 423 444 273 440 438 226 292 418 115 81 420 412 342 263 446 219 114 108 38 253 146 54 496 150 450 103 147 44 19 353 80 310 70 384 91 13 413 386 161 396 61 349 409 221 367 96 322 227 433 201 231 175 64 290 402 495 373 233 211 94 162 31 95 176 330 289 295 52 102...
output:
15999 120397645 791732988
result:
points 0.73336666670
Test #22:
score: 66.003
Acceptable Answer
time: 185ms
memory: 8880kb
input:
2 494 154 75 65 20 92 153 39 236 177 41 482 47 298 426 124 228 494 381 473 364 128 109 340 57 432 480 144 43 184 392 286 359 291 423 469 260 468 355 146 231 28 235 62 188 134 138 305 87 175 362 95 58 116 250 464 297 254 407 212 32 160 316 453 396 18 243 338 272 252 454 199 422 249 418 450 185 356 39...
output:
15999 120397645 192551329
result:
points 0.73336666670
Test #23:
score: 66.003
Acceptable Answer
time: 181ms
memory: 8864kb
input:
2 493 118 473 190 268 244 72 211 196 153 261 12 76 245 365 371 162 302 352 112 272 273 425 340 354 234 220 45 65 231 321 290 285 383 389 83 133 248 260 376 326 214 33 478 323 3 373 334 437 212 457 337 47 81 113 339 379 173 421 223 253 48 314 312 55 408 363 258 42 160 289 82 239 472 359 415 465 80 35...
output:
15999 120397645 506886456
result:
points 0.73336666670
Test #24:
score: 66.003
Acceptable Answer
time: 183ms
memory: 9080kb
input:
2 493 491 357 122 219 398 79 375 33 186 118 298 2 206 132 140 99 465 251 350 120 474 35 218 131 355 173 158 478 388 349 100 418 149 156 124 482 437 221 200 29 31 61 489 208 414 188 479 358 72 134 52 416 263 88 187 115 392 104 214 233 48 74 411 146 341 332 71 144 351 32 477 265 421 461 238 352 222 20...
output:
15999 120397645 908595790
result:
points 0.73336666670
Test #25:
score: 66.003
Acceptable Answer
time: 197ms
memory: 9168kb
input:
2 494 456 311 174 150 206 61 33 444 53 256 331 131 148 105 1 370 133 269 406 407 310 29 293 153 232 469 122 480 334 300 195 94 422 59 36 308 217 288 193 197 476 392 239 417 204 222 50 488 491 432 181 77 137 145 23 64 276 90 250 106 270 76 179 173 279 164 34 12 124 388 182 4 273 474 154 235 87 291 21...
output:
15999 120397645 270167063
result:
points 0.73336666670
Test #26:
score: 66.003
Acceptable Answer
time: 187ms
memory: 8892kb
input:
2 500 454 477 317 465 497 59 428 162 66 19 144 293 396 332 404 381 184 330 469 476 187 96 92 114 296 119 152 20 218 110 417 61 10 173 56 385 350 470 389 192 165 429 243 25 325 359 94 401 288 340 183 190 137 366 194 89 500 252 103 392 356 8 175 88 6 220 221 322 108 46 15 134 98 121 5 199 277 105 453 ...
output:
15999 120397645 721976537
result:
points 0.73336666670
Test #27:
score: 66.003
Acceptable Answer
time: 186ms
memory: 9104kb
input:
2 499 106 154 51 308 314 251 211 424 476 279 11 33 441 226 132 233 388 55 153 430 322 466 232 30 71 218 48 67 285 317 345 219 220 473 378 293 56 422 142 451 239 241 456 2 370 409 117 309 152 341 377 471 198 7 134 170 301 62 302 438 349 222 131 12 41 284 497 209 176 121 3 420 163 407 468 18 141 405 3...
output:
15999 120397645 377700749
result:
points 0.73336666670
Test #28:
score: 66.003
Acceptable Answer
time: 183ms
memory: 8888kb
input:
2 495 423 23 335 113 489 190 353 192 20 420 126 200 428 288 329 247 457 487 94 58 439 331 25 289 401 97 95 80 488 389 171 176 79 153 410 185 444 223 193 84 201 93 89 239 441 469 285 385 112 54 486 375 120 82 330 21 350 491 316 429 136 433 104 337 49 460 338 109 290 319 14 286 314 406 356 218 449 61 ...
output:
15999 120397645 897331140
result:
points 0.73336666670
Test #29:
score: 0
Wrong Answer
time: 183ms
memory: 9084kb
input:
2 499 457 89 410 105 251 213 370 21 400 343 112 363 127 246 67 295 46 450 401 181 204 280 197 362 499 385 178 75 36 24 226 34 313 155 309 38 383 311 284 236 8 217 461 4 406 39 434 238 119 439 224 374 129 87 120 43 244 388 276 165 272 211 292 492 498 287 28 467 124 209 445 344 184 33 416 373 130 351 ...
output:
0 0 0
result:
FAIL WA