QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#497010 | #6550. Elimination Race | pandapythoner | TL | 102ms | 5676kb | C++23 | 4.1kb | 2024-07-28 18:02:24 | 2024-07-28 18:02:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for(int i = 0; i < n; i += 1)
#define len(a) ((int)(a).size())
const ll inf = 1e18;
mt19937 rnd(234);
int n;
vector<vector<int>> p, pos;
int cur_racer;
vector<int> matched;
int usdc = -1;
vector<int> usd;
vector<int> bro;
bool dfs(int v) {
usd[v] = usdc;
for (int i = pos[v][cur_racer] + 1; i < n; i += 1) {
int to = p[v][i];
if (bro[to] == -1) {
bro[to] = v;
matched[v] = true;
return true;
}
if (usd[bro[to]] != usdc) {
if (dfs(bro[to])) {
bro[to] = v;
matched[v] = true;
return true;
}
}
}
return false;
}
vector<int> build_answer() {
vector<int> cur_index(n - 1), cur_last(n - 1, n - 1);
rep(i, n) {
if (bro[i] != -1) {
cur_index[bro[i]] = pos[bro[i]][i];
}
}
vector<int> eliminated(n, false);
eliminated[cur_racer] = true;
vector<int> usd(n - 1, false);
vector<int> result;
while (len(result) < n - 1) {
while (1) {
bool changed = false;
rep(i, n - 1) {
if (usd[i]) continue;
while (eliminated[p[i][cur_last[i]]]) {
cur_last[i] -= 1;
changed = true;
}
if (cur_index[i] == cur_last[i]) {
result.push_back(i);
usd[i] = true;
eliminated[p[i][cur_index[i]]] = true;
changed = true;
}
}
if (!changed) {
break;
}
}
int u = -1;
rep(i, n - 1) {
if (!usd[i] and cur_index[i] < cur_last[i]) {
u = i;
}
}
if (u != -1) {
vector<int> deletion_pos(n, -1);
rep(i, n - 1) {
if (!usd[i]) {
deletion_pos[p[i][cur_index[i]]] = i;
}
}
rep(i, n) if (!eliminated[i]) assert(deletion_pos[i] != -1);
rep(i, n) {
u = deletion_pos[p[u][cur_last[u]]];
}
vector<int> cycle;
int v = u;
while (1) {
cycle.push_back(v);
v = deletion_pos[p[v][cur_last[v]]];
if (v == u) {
break;
}
}
for (auto v : cycle) {
cur_index[v] = cur_last[v];
}
}
}
return result;
}
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
cin >> n;
p.assign(n - 1, vector<int>(n));
pos.assign(n - 1, vector<int>(n));
rep(i, n - 1) {
rep(j, n) {
int x; cin >> x; --x;
p[i][j] = x;
pos[i][x] = j;
}
}
usd.assign(n - 1, 0);
usdc = 1;
for (cur_racer = 0; cur_racer < n; cur_racer += 1) {
matched.assign(n - 1, false);
++usdc;
bro.assign(n, -1);
while (1) {
++usdc;
bool flag = false;
rep(v, n - 1) {
if (!matched[v] and usd[v] != usdc) {
if (dfs(v)) {
flag = true;
}
}
}
if (!flag) {
break;
}
}
int cnt = 0;
rep(i, n) {
if (bro[i] != -1) {
cnt += 1;
}
}
assert(0 <= cnt and cnt <= n - 1);
if (cnt == n - 1) {
cout << "Yes" << "\n";
vector<int> result = build_answer();
for (auto x : result) {
cout << x + 1 << " ";
}
cout << "\n";
} else {
cout << "No" << "\n";
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3540kb
input:
4 1 2 3 4 2 1 3 4 4 3 1 2
output:
Yes 2 3 1 No No No
result:
ok n=4, yes=1, no=3
Test #2:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
3 2 1 3 2 1 3
output:
No Yes 2 1 No
result:
ok n=3, yes=1, no=2
Test #3:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
2 1 2
output:
Yes 1 No
result:
ok n=2, yes=1, no=1
Test #4:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
2 2 1
output:
No Yes 1
result:
ok n=2, yes=1, no=1
Test #5:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
11 4 3 6 1 11 10 5 7 8 9 2 11 6 5 1 10 3 8 2 7 9 4 5 9 2 11 3 4 1 10 8 6 7 9 11 8 3 5 4 1 6 7 10 2 3 9 7 6 5 10 1 4 11 8 2 8 2 4 1 5 9 3 7 6 10 11 3 8 2 9 1 4 5 10 11 6 7 10 11 4 1 7 5 2 6 8 9 3 10 6 9 3 2 1 4 8 11 7 5 8 11 9 1 4 10 2 5 3 7 6
output:
Yes 4 10 2 7 8 9 3 5 1 6 No No No No No No Yes 5 8 1 2 3 4 6 9 10 7 Yes 1 2 8 9 4 5 10 3 6 7 Yes 4 6 7 10 3 1 9 2 5 8 No
result:
ok n=11, yes=4, no=7
Test #6:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
11 6 7 8 9 3 4 1 11 5 10 2 7 10 6 3 1 2 5 11 4 9 8 4 3 9 1 10 2 5 7 6 8 11 10 4 2 11 8 1 5 7 9 6 3 11 9 4 6 8 2 1 7 3 5 10 9 10 2 7 4 11 6 1 3 8 5 11 8 4 9 7 1 2 10 5 3 6 5 7 9 10 1 8 4 2 6 11 3 4 2 9 7 10 1 6 8 3 5 11 2 7 6 10 5 11 1 8 4 9 3
output:
Yes 1 7 9 2 6 3 4 5 8 10 No No Yes 10 1 4 6 8 5 9 2 3 7 No No Yes 1 2 5 8 3 4 9 10 7 6 No Yes 2 9 10 4 5 8 3 6 7 1 No No
result:
ok n=11, yes=4, no=7
Test #7:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
11 3 5 9 7 4 1 8 11 10 2 6 9 7 10 4 8 3 1 6 5 2 11 9 5 11 3 8 7 1 6 2 4 10 8 9 11 1 4 3 10 6 7 2 5 11 3 7 8 5 9 1 2 10 6 4 8 3 10 11 1 4 2 5 6 7 9 5 9 10 2 4 3 7 1 11 6 8 11 8 10 3 5 7 4 1 2 6 9 7 8 1 9 10 5 3 11 2 6 4 2 4 6 9 5 11 7 1 8 10 3
output:
Yes 8 1 2 4 6 7 9 10 5 3 No No No No No Yes 6 8 10 1 4 9 2 5 7 3 No No No No
result:
ok n=11, yes=2, no=9
Test #8:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
11 3 5 9 2 11 1 4 8 6 10 7 8 3 4 9 1 5 6 2 7 10 11 10 6 4 7 11 9 1 3 5 8 2 9 3 2 7 8 4 5 10 1 11 6 3 4 9 10 1 8 2 7 6 11 5 9 4 7 8 1 11 6 3 5 2 10 5 11 4 10 6 3 2 1 9 8 7 10 11 8 5 2 1 9 7 4 6 3 6 3 8 9 4 11 1 2 10 7 5 8 3 11 10 9 1 6 5 7 2 4
output:
Yes 1 2 3 4 6 8 9 10 5 7 No No No No No No Yes 3 7 1 2 4 5 8 10 6 9 Yes 5 6 10 1 3 4 7 8 2 9 No No
result:
ok n=11, yes=3, no=8
Test #9:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
11 3 5 7 10 9 6 2 1 11 8 4 3 6 1 7 5 11 4 10 9 8 2 10 4 6 7 11 3 1 2 9 5 8 10 4 1 9 11 5 3 8 6 7 2 11 5 9 1 10 4 8 6 7 2 3 3 2 7 9 11 10 1 5 8 4 6 4 5 11 8 6 7 10 1 2 3 9 2 7 3 11 8 1 9 6 4 10 5 4 8 2 7 5 10 6 1 11 3 9 9 6 3 5 1 10 11 7 8 4 2
output:
Yes 1 3 4 5 7 9 2 10 6 8 No No No No No Yes 4 5 10 6 9 7 2 8 3 1 No No Yes 8 1 4 2 5 7 9 10 3 6 Yes 1 10 5 9 3 4 6 7 8 2
result:
ok n=11, yes=4, no=7
Test #10:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
11 6 5 11 2 8 9 7 10 1 4 3 11 4 3 6 10 7 9 1 8 5 2 3 2 6 8 5 7 9 1 10 4 11 11 6 9 1 3 10 4 2 7 8 5 5 6 8 7 11 9 1 3 4 2 10 6 5 3 9 2 1 10 11 8 4 7 9 3 4 6 2 1 5 7 8 10 11 11 6 9 8 1 4 3 2 5 10 7 6 4 7 11 3 2 1 5 8 10 9 10 3 8 6 4 1 11 7 9 2 5
output:
No No No Yes 1 3 5 6 8 4 7 9 10 2 No Yes 1 2 5 6 7 10 3 4 8 9 No Yes 2 4 7 3 5 6 8 9 1 10 No No No
result:
ok n=11, yes=3, no=8
Test #11:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
11 10 5 4 6 11 1 3 7 9 8 2 2 8 10 4 6 1 7 9 3 11 5 5 7 11 8 3 1 9 2 4 10 6 5 6 11 10 3 1 2 9 8 4 7 6 3 4 9 11 5 1 2 8 10 7 8 7 6 1 10 3 5 11 9 4 2 5 11 9 4 6 2 7 1 8 3 10 10 11 2 1 9 4 3 5 8 6 7 9 3 4 6 5 1 11 8 2 7 10 7 10 4 5 9 6 8 1 3 11 2
output:
Yes 2 3 7 1 4 5 6 9 10 8 No Yes 2 7 1 4 10 8 9 3 5 6 Yes 4 6 10 1 3 7 2 8 9 5 No No No Yes 1 2 10 5 8 9 4 7 3 6 Yes 1 6 3 5 7 10 4 8 9 2 No Yes 2 10 6 4 9 1 3 5 7 8
result:
ok n=11, yes=6, no=5
Test #12:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
11 7 8 4 5 1 3 6 9 11 10 2 8 10 9 7 1 3 5 4 2 11 6 4 11 9 5 3 1 2 10 8 6 7 9 6 7 1 3 8 2 4 10 5 11 9 3 10 2 4 1 6 7 5 11 8 9 3 1 7 2 6 5 8 11 4 10 2 4 9 3 1 5 11 6 7 8 10 3 4 11 10 8 6 1 5 2 7 9 4 11 7 6 8 1 10 9 3 5 2 8 7 4 9 10 3 1 5 2 6 11
output:
Yes 8 6 9 3 5 1 7 10 4 2 No Yes 1 3 4 5 6 7 8 9 10 2 Yes 6 7 8 2 3 5 9 4 1 10 Yes 4 5 6 7 8 9 10 2 1 3 No No No No No No
result:
ok n=11, yes=4, no=7
Test #13:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
11 4 8 10 9 6 3 1 5 2 7 11 10 8 7 4 9 1 6 11 3 2 5 3 10 11 6 1 4 5 2 7 9 8 4 9 8 3 1 6 11 7 5 2 10 8 2 11 7 3 1 5 6 10 4 9 4 9 3 6 5 1 7 10 11 2 8 4 3 6 7 1 5 8 2 9 11 10 10 7 4 1 9 8 2 3 6 11 5 10 7 2 8 5 1 11 6 4 3 9 7 6 9 8 1 11 5 4 2 3 10
output:
Yes 1 4 5 8 9 10 2 7 6 3 Yes 1 2 4 6 7 8 10 3 9 5 Yes 9 10 5 3 7 1 2 6 8 4 Yes 5 9 1 7 10 6 8 3 4 2 No Yes 9 3 5 6 10 4 8 2 1 7 Yes 1 4 6 8 3 2 5 7 9 10 No No No No
result:
ok n=11, yes=6, no=5
Test #14:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
11 8 5 9 7 6 1 10 4 2 3 11 3 6 5 11 9 7 1 2 4 10 8 2 11 3 8 1 6 7 5 4 10 9 7 5 8 6 4 9 1 2 3 10 11 6 7 8 1 2 3 11 9 10 5 4 7 4 10 9 1 2 8 5 11 3 6 10 7 5 6 11 3 1 2 9 4 8 5 2 6 8 10 1 9 3 4 7 11 5 7 3 11 8 2 1 6 9 4 10 2 3 10 4 1 11 5 7 8 9 6
output:
Yes 5 8 1 4 6 7 9 2 3 10 Yes 1 4 8 3 7 2 9 5 6 10 Yes 1 4 6 8 5 10 2 3 7 9 No Yes 5 1 6 2 3 4 10 7 8 9 No Yes 8 1 6 9 10 3 4 5 7 2 No No No No
result:
ok n=11, yes=5, no=6
Test #15:
score: 0
Accepted
time: 93ms
memory: 5660kb
input:
500 446 156 267 294 482 398 430 13 311 318 474 426 140 484 83 387 257 136 69 305 295 283 287 55 52 65 322 249 43 56 331 443 226 214 341 182 389 464 84 477 187 40 327 411 248 10 223 165 379 293 12 9 5 230 309 367 2 397 265 59 361 118 196 316 390 213 194 167 483 452 114 345 263 219 87 94 160 224 200 2...
output:
Yes 92 143 301 303 379 442 458 478 496 6 50 58 96 123 152 168 175 213 239 254 310 328 331 435 472 477 498 2 25 32 87 90 97 99 100 104 119 124 140 149 154 166 177 184 185 191 193 197 208 215 218 221 230 234 242 289 305 311 312 322 329 337 346 357 360 362 367 388 404 409 410 417 436 452 456 483 488 49...
result:
ok n=500, yes=171, no=329
Test #16:
score: 0
Accepted
time: 100ms
memory: 5648kb
input:
500 18 271 51 335 212 326 93 264 408 66 230 181 456 149 259 396 269 443 136 446 250 409 240 457 319 289 402 334 247 216 106 214 468 448 58 186 137 225 337 487 281 333 130 275 169 420 100 71 57 284 63 454 108 375 164 437 133 110 440 350 479 370 276 211 193 148 198 222 496 460 308 85 286 242 257 435 4...
output:
Yes 36 57 76 118 182 202 335 349 362 386 18 65 263 280 336 413 24 25 27 35 85 102 103 122 129 144 179 194 211 226 236 258 314 334 358 374 408 429 433 453 45 162 189 299 435 460 12 19 56 73 86 100 109 127 143 170 173 183 187 225 250 253 262 272 274 291 292 298 306 341 342 351 366 15 20 28 41 42 58 87...
result:
ok n=500, yes=185, no=315
Test #17:
score: 0
Accepted
time: 93ms
memory: 5664kb
input:
500 24 261 411 242 116 202 460 6 169 140 268 333 447 468 341 373 58 274 175 180 77 232 465 326 300 211 204 75 98 425 322 90 408 489 227 480 89 31 94 248 334 299 76 290 157 178 111 143 103 117 131 292 456 201 118 285 150 10 56 251 418 448 453 47 451 184 343 42 210 68 113 422 165 391 415 272 45 82 490...
output:
Yes 81 88 205 217 429 58 69 90 230 245 29 65 92 175 243 272 279 321 357 358 361 377 488 493 30 80 96 98 150 202 294 308 352 356 365 394 465 483 2 3 17 38 54 101 130 143 174 216 273 332 336 348 355 367 381 411 460 467 482 487 492 7 15 19 34 55 62 73 75 78 99 100 102 112 114 116 119 162 164 166 172 17...
result:
ok n=500, yes=186, no=314
Test #18:
score: 0
Accepted
time: 102ms
memory: 5608kb
input:
500 219 142 183 492 426 414 85 228 482 93 21 361 327 345 234 50 432 52 498 223 372 127 319 56 263 210 204 43 394 271 22 437 419 486 186 255 398 167 353 444 371 172 23 270 235 133 189 6 279 380 97 179 2 29 277 328 149 411 158 369 298 26 489 315 107 360 160 463 109 215 81 232 448 140 355 33 82 25 125 ...
output:
Yes 27 31 48 49 103 113 180 243 278 339 438 449 462 487 52 73 90 110 128 191 209 242 275 298 300 301 311 330 343 440 493 23 136 253 303 393 395 19 21 80 102 129 130 162 203 204 227 257 270 286 292 308 320 321 335 385 404 431 436 439 457 463 54 93 261 291 406 1 16 50 108 156 226 250 351 359 426 450 4...
result:
ok n=500, yes=188, no=312
Test #19:
score: 0
Accepted
time: 96ms
memory: 5576kb
input:
500 330 206 369 65 187 249 174 325 166 260 55 244 351 275 118 186 434 116 489 481 331 472 112 130 297 26 16 84 321 132 484 305 188 35 287 452 109 44 180 407 374 46 221 29 246 424 208 292 285 209 414 418 33 406 223 309 422 108 56 359 296 326 49 286 217 173 120 72 322 62 204 451 81 455 179 45 284 298 ...
output:
Yes 144 145 246 343 384 414 444 447 494 138 158 206 308 7 21 51 68 95 99 112 114 121 136 143 167 173 185 186 201 213 230 234 257 280 318 336 344 352 356 358 402 429 38 76 195 209 319 351 423 491 41 141 172 239 253 295 433 457 23 43 48 52 57 58 59 83 87 108 131 132 133 137 148 204 220 222 240 245 269...
result:
ok n=500, yes=175, no=325
Test #20:
score: 0
Accepted
time: 94ms
memory: 5588kb
input:
500 233 154 203 96 30 404 476 284 75 447 291 52 155 197 258 500 338 278 199 20 405 408 307 108 122 368 424 308 453 26 7 94 330 177 319 407 105 179 236 337 150 315 29 345 292 471 89 456 180 483 382 466 45 485 263 376 478 53 61 34 463 327 219 472 62 84 172 443 226 432 190 63 366 276 174 168 375 147 19...
output:
Yes 7 68 71 188 202 220 279 282 355 424 496 21 34 45 50 56 73 83 98 99 147 150 153 173 218 256 273 275 294 308 360 368 370 396 420 436 441 470 477 486 488 6 11 51 190 225 235 240 328 14 30 32 33 40 47 54 66 91 95 128 139 141 175 177 184 223 233 245 261 269 271 276 280 296 298 316 324 340 342 373 395...
result:
ok n=500, yes=182, no=318
Test #21:
score: 0
Accepted
time: 97ms
memory: 5668kb
input:
500 147 88 258 111 242 490 363 484 137 17 81 260 58 113 14 50 286 333 479 419 398 240 309 301 210 289 296 83 357 120 9 288 459 232 146 239 426 319 3 171 247 348 207 412 233 32 116 480 56 115 492 218 331 209 86 174 16 101 350 176 245 36 456 365 199 102 94 76 82 351 376 103 455 420 231 325 37 93 214 2...
output:
Yes 10 45 133 169 211 254 257 273 335 365 369 377 415 419 455 495 4 53 79 85 96 104 107 130 143 153 191 192 220 242 263 287 294 296 301 318 319 338 343 347 381 410 413 428 429 430 448 450 452 485 497 5 16 19 36 249 261 274 313 396 426 440 472 33 38 118 137 170 208 292 295 333 418 465 32 134 135 194 ...
result:
ok n=500, yes=180, no=320
Test #22:
score: 0
Accepted
time: 95ms
memory: 5672kb
input:
500 170 302 411 359 201 15 194 287 128 106 181 12 367 450 339 488 377 466 115 16 275 62 178 330 276 461 168 58 380 202 14 37 233 92 383 195 459 327 74 477 278 363 444 342 422 455 28 169 301 492 436 337 356 487 126 378 404 249 7 259 366 187 103 447 130 389 24 120 245 206 47 432 416 102 297 166 376 31...
output:
Yes 121 392 51 75 86 89 95 100 146 148 203 215 227 249 275 317 318 336 349 356 415 485 106 211 323 376 412 439 26 180 222 269 373 429 458 21 25 30 37 42 46 56 101 107 114 131 145 147 150 153 171 175 219 260 273 283 287 294 394 403 407 427 436 456 22 65 84 136 191 202 232 337 342 371 408 421 16 24 33...
result:
ok n=500, yes=174, no=326
Test #23:
score: 0
Accepted
time: 101ms
memory: 5608kb
input:
500 498 451 475 72 77 397 157 119 386 312 321 45 71 21 24 438 186 26 341 408 39 195 275 366 100 144 70 95 246 4 46 361 182 155 473 387 23 335 6 413 292 416 89 266 2 457 450 213 367 22 92 382 237 170 251 500 254 309 136 323 27 42 222 481 111 169 188 371 166 150 434 427 208 209 398 430 165 295 238 258...
output:
Yes 3 18 22 26 27 37 45 62 68 105 108 124 148 153 158 209 227 231 242 246 286 326 339 358 367 385 388 392 400 404 411 413 419 424 437 443 448 449 464 479 484 497 8 55 111 126 272 317 366 371 380 422 488 46 189 256 260 273 289 290 293 295 298 428 182 229 347 33 60 89 101 274 338 346 426 477 4 21 128 ...
result:
ok n=500, yes=187, no=313
Test #24:
score: 0
Accepted
time: 97ms
memory: 5676kb
input:
500 74 364 86 239 403 250 29 92 464 201 114 394 231 279 59 217 343 242 225 255 48 154 404 103 183 18 159 147 137 222 75 172 458 362 39 99 396 149 100 428 259 318 53 460 76 163 146 444 342 184 143 296 262 186 148 175 165 241 294 218 254 482 16 488 169 78 27 101 311 63 14 258 117 60 393 107 410 145 10...
output:
Yes 2 19 31 50 58 68 93 99 116 158 164 166 174 176 199 205 233 245 259 263 266 268 343 362 364 374 383 403 410 431 432 443 447 454 458 470 472 473 498 11 16 17 70 249 250 294 350 5 45 59 71 100 167 216 330 360 428 430 455 14 169 185 221 286 387 8 53 76 88 118 150 153 198 253 262 275 300 315 407 420 ...
result:
ok n=500, yes=177, no=323
Test #25:
score: -100
Time Limit Exceeded
input:
500 468 261 329 368 419 490 308 362 265 282 392 397 306 281 384 325 263 319 448 449 277 333 323 394 351 472 442 260 374 400 274 264 423 278 369 380 403 303 406 470 295 318 326 268 371 339 491 390 444 481 421 459 393 347 383 408 257 324 286 267 253 436 483 460 427 320 388 297 287 363 288 358 361 331 ...
output:
No Yes 302 69 147 400 51 87 101 104 106 123 165 185 212 265 268 272 278 310 324 325 346 360 420 445 109 155 157 162 171 258 305 366 454 497 11 29 76 80 114 127 158 159 200 242 284 288 326 409 416 417 459 105 196 205 249 355 75 85 93 103 111 137 195 331 407 438 471 499 73 124 280 322 344 361 393 481 ...