QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #105690 | #4791. Movies | Determinant | WA | 18ms | 4744kb | C++14 | 1.0kb | 2023-05-14 21:27:42 | 2023-05-14 21:27:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;const int N=1e5+7;
int n,m,ans=1e9,minn=1e9,fl=1,a[N],b[N],c[N];
int sum(int x){return x==n?m:a[c[x]]-x;}
int sum(int x,int y){return sum(y)-sum(x);}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){scanf("%d",&a[i]);b[i]=a[i];if(a[i]>a[i-1])fl=0;}
if(fl){puts("0");return 0;}sort(b+1,b+n+1);
for(int i=1;i<=n;++i)c[lower_bound(b+1,b+n+1,a[i])-b]=i;
for(int r=1,l=1;r<n;++r){
if(c[r]<c[r-1])l=r;int x=max(2*(l-1)-1,2*(n-1-r)),L,R,fl;
if(sum(l-1,r+1)>=x)ans=min(ans,x);
else{
x=sum(l-1,r+1),fl=(x+1)%2;
L=max(l-1-(x+1)/2,0);
R=max(n-1-r-x/2,0);
if(!L){if(sum(0,l-1)>=R*2-(fl==0))ans=min(ans,x+R*2-(fl==0));}
else if(!R){if(sum(r+1,n)>=L*2-(fl==1))ans=min(ans,x+R*2-(fl==0));}
else{
if(sum(r+1,n)>=L*2-(fl==1)&&sum(0,l-1)>=(L+R)*2-1)
ans=min(ans,x+L*2-(fl==1)+(L+R)*2-1);
if(sum(0,l-1)>=R*2-(fl==0)&&sum(r+1,n)>=(R+L)*2-1)
ans=min(ans,x+R*2-(fl==0)+(R+L)*2-1);
}
}
}
printf("%d\n",ans==1e9?-1:ans+1);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3520kb
input:
5 5 3 1 5 2 4 6 8 7 9 10
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3576kb
input:
5 10 3 5 9 15 4 6 11 13 1 7 10 12 14 2 8
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3684kb
input:
5 10 14 15 4 12 1 3 9 6 10 13 2 11 7 5 8
output:
3
result:
ok 1 number(s): "3"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
10 10 13 10 4 11 2 15 14 16 1 17 20 18 8 19 6 5 3 9 12 7
output:
-1
result:
ok 1 number(s): "-1"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3504kb
input:
10 10 20 3 17 8 10 6 18 15 14 19 11 9 13 16 4 7 12 5 1 2
output:
9
result:
ok 1 number(s): "9"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3496kb
input:
8 12 1 6 20 13 3 5 9 17 7 2 14 11 19 16 12 18 4 15 10 8
output:
6
result:
ok 1 number(s): "6"
Test #7:
score: 0
Accepted
time: 2ms
memory: 3596kb
input:
10 10 9 6 16 10 18 5 20 17 13 1 14 8 19 2 12 11 3 7 4 15
output:
7
result:
ok 1 number(s): "7"
Test #8:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
10 10 7 2 19 5 20 4 14 15 9 16 17 8 12 11 13 10 1 3 6 18
output:
9
result:
ok 1 number(s): "9"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
10 10 9 20 2 13 15 10 16 19 1 4 3 11 7 14 12 8 6 17 18 5
output:
-1
result:
ok 1 number(s): "-1"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
10 10 10 14 6 7 11 8 18 19 15 12 5 17 20 16 2 1 9 4 3 13
output:
-1
result:
ok 1 number(s): "-1"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
50 100 115 22 37 125 124 62 47 145 88 126 134 127 77 121 148 25 120 21 42 17 75 138 144 76 109 13 78 82 102 5 32 143 52 72 69 18 67 92 133 56 9 38 89 15 61 7 137 6 1 58 107 147 54 98 73 31 3 40 71 87 140 136 2 60 130 44 50 59 93 90 70 36 149 105 11 68 63 79 119 96 106 8 30 51 108 94 141 12 122 14 49...
output:
-1
result:
ok 1 number(s): "-1"
Test #12:
score: 0
Accepted
time: 2ms
memory: 3568kb
input:
50 100 69 63 30 79 36 27 46 57 28 98 19 15 18 75 77 76 86 74 131 78 60 33 11 40 24 116 71 109 23 111 99 87 58 103 132 119 55 66 122 54 128 43 130 147 94 125 90 144 105 148 89 51 41 84 81 88 100 12 82 17 118 126 93 143 101 64 145 3 134 5 13 62 7 6 133 31 26 138 16 2 129 110 65 102 108 114 35 10 115 9...
output:
-1
result:
ok 1 number(s): "-1"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
50 100 72 7 130 30 87 104 4 32 11 46 111 49 35 124 12 67 36 26 13 143 45 92 33 8 125 148 59 127 114 55 68 41 98 83 19 99 108 28 47 115 90 135 15 56 65 48 93 101 138 84 22 6 121 40 57 53 37 105 116 34 21 75 64 80 70 16 5 91 73 9 103 25 2 71 58 61 86 133 120 137 150 126 94 134 119 147 97 82 18 145 42 ...
output:
-1
result:
ok 1 number(s): "-1"
Test #14:
score: 0
Accepted
time: 2ms
memory: 3752kb
input:
50 100 32 24 115 62 144 61 118 21 84 68 9 30 114 79 27 19 147 75 35 73 4 90 71 111 140 18 88 81 26 102 59 78 77 103 16 138 12 33 145 150 44 148 107 28 11 42 124 109 143 128 38 31 131 97 58 104 25 76 41 15 74 43 53 110 85 70 57 91 92 80 86 5 83 64 96 116 95 133 93 1 105 139 66 141 37 23 14 50 106 113...
output:
-1
result:
ok 1 number(s): "-1"
Test #15:
score: 0
Accepted
time: 1ms
memory: 3744kb
input:
50 100 105 22 115 6 88 101 42 41 18 111 39 4 63 3 52 142 84 48 119 85 89 110 73 86 53 143 117 129 62 30 98 116 40 25 123 113 130 103 45 95 128 75 148 106 145 38 20 125 118 82 81 23 15 55 8 9 92 77 91 2 144 97 132 11 147 102 33 137 71 121 133 29 107 27 1 99 134 93 90 21 112 50 28 26 24 114 96 12 122 ...
output:
-1
result:
ok 1 number(s): "-1"
Test #16:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
50 100 2 29 6 31 23 19 4 10 36 32 69 78 50 24 13 92 61 58 70 18 110 42 56 99 129 26 43 91 75 86 115 97 95 102 64 53 117 88 139 145 108 132 147 149 121 150 116 138 142 146 65 80 123 126 93 136 89 113 74 106 94 52 125 134 77 111 48 118 87 144 41 49 71 109 17 5 40 25 33 82 39 62 30 7 141 8 9 21 28 45 2...
output:
-1
result:
ok 1 number(s): "-1"
Test #17:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
50 100 2 5 9 12 14 15 20 21 22 26 33 30 34 36 38 42 44 43 47 49 48 55 57 60 67 69 75 79 78 81 82 85 90 100 91 99 108 109 112 116 124 115 119 125 127 129 143 148 147 150 17 16 80 102 11 3 25 142 23 137 131 7 123 110 54 65 118 113 19 149 92 56 29 46 31 70 96 77 106 146 120 53 37 84 95 134 141 139 72 7...
output:
80
result:
ok 1 number(s): "80"
Test #18:
score: 0
Accepted
time: 1ms
memory: 3684kb
input:
60 100 3 6 5 7 15 13 17 22 20 33 25 34 24 28 35 31 42 39 43 50 53 54 62 56 75 58 65 86 70 73 87 88 91 94 101 92 98 102 110 106 112 111 121 116 127 124 130 131 128 134 141 132 145 149 147 155 154 160 158 156 103 142 72 85 83 79 129 115 123 81 61 144 133 51 27 109 125 60 150 96 104 29 40 49 114 76 137...
output:
-1
result:
ok 1 number(s): "-1"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
60 200 12 3 13 17 30 22 19 49 33 47 43 55 56 57 80 82 90 81 113 106 111 124 118 123 135 139 133 140 137 138 147 152 141 150 154 166 165 186 170 173 185 189 187 195 198 196 212 197 210 213 228 230 231 242 235 240 243 250 247 254 208 73 36 34 163 102 161 159 221 69 18 164 76 63 153 206 239 224 28 184 ...
output:
87
result:
ok 1 number(s): "87"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
75 200 3 8 19 12 29 18 44 32 51 37 25 39 49 79 59 64 63 67 73 81 76 95 80 94 87 89 102 90 100 110 116 117 108 112 120 124 131 121 150 140 145 161 144 149 164 167 156 154 198 170 166 185 214 184 190 186 211 207 201 202 225 203 212 222 230 236 231 238 262 243 254 260 273 272 275 160 228 200 268 30 82 ...
output:
-1
result:
ok 1 number(s): "-1"
Test #21:
score: 0
Accepted
time: 2ms
memory: 3752kb
input:
75 225 12 13 15 36 23 38 49 39 53 51 52 72 76 64 55 66 80 89 75 92 99 83 90 114 96 111 101 107 135 104 146 112 126 152 120 137 153 160 162 151 159 163 171 165 161 169 203 177 209 190 219 248 229 222 210 237 254 256 239 241 260 255 245 274 262 261 276 289 270 286 287 297 294 299 300 148 236 73 154 68...
output:
171
result:
ok 1 number(s): "171"
Test #22:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
200 600 30 8 94 72 29 7 104 23 107 37 32 73 33 19 31 149 49 111 11 84 146 21 117 121 115 127 57 74 53 156 169 177 22 210 165 85 274 188 183 246 193 71 40 288 231 128 142 221 206 283 66 222 167 280 209 241 199 304 201 166 285 215 130 144 227 195 303 346 321 299 161 359 259 296 265 301 257 271 354 338...
output:
558
result:
ok 1 number(s): "558"
Test #23:
score: 0
Accepted
time: 2ms
memory: 3600kb
input:
200 600 1 40 26 8 45 30 44 41 48 61 112 24 171 10 65 4 56 53 143 209 6 204 111 185 34 109 36 127 51 230 5 126 77 222 235 107 338 179 158 318 186 162 238 102 173 271 115 177 193 164 58 150 229 258 189 197 289 170 243 248 369 277 223 291 272 264 265 316 287 328 275 394 390 321 211 373 262 347 304 408 ...
output:
-1
result:
ok 1 number(s): "-1"
Test #24:
score: 0
Accepted
time: 2ms
memory: 3580kb
input:
200 600 19 58 5 73 2 42 25 11 162 99 85 7 75 81 121 129 115 53 36 48 45 170 49 24 177 276 31 102 116 185 22 110 71 72 66 157 74 101 225 122 188 172 186 228 54 193 153 113 154 70 168 338 263 224 119 271 364 268 187 202 230 216 253 269 316 218 280 175 140 408 239 353 334 357 222 150 256 209 339 389 31...
output:
-1
result:
ok 1 number(s): "-1"
Test #25:
score: 0
Accepted
time: 2ms
memory: 3496kb
input:
200 600 80 34 63 20 12 36 50 66 11 71 46 60 129 57 56 54 48 62 115 93 31 103 142 89 104 149 252 156 65 111 196 277 159 219 223 102 72 254 130 210 212 126 202 296 55 207 244 172 276 191 168 269 270 152 239 240 230 352 232 189 220 397 226 311 318 289 312 320 393 330 291 350 282 365 314 237 332 400 419...
output:
-1
result:
ok 1 number(s): "-1"
Test #26:
score: 0
Accepted
time: 2ms
memory: 3744kb
input:
200 700 53 56 68 293 50 31 62 76 60 95 8 75 48 125 114 90 129 92 137 88 96 119 109 179 102 211 181 223 152 6 100 159 275 127 156 202 226 139 196 333 229 284 257 144 198 341 262 207 260 326 271 235 164 237 89 171 286 173 324 336 328 468 292 338 317 281 330 304 381 491 380 344 379 402 241 369 463 389 ...
output:
552
result:
ok 1 number(s): "552"
Test #27:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
200 700 37 85 67 40 109 82 53 119 105 63 91 157 183 11 74 156 148 47 149 167 39 215 136 194 29 168 161 291 127 158 174 137 182 294 267 188 178 110 135 217 243 209 355 73 324 242 253 269 289 97 160 345 263 202 331 349 255 346 329 228 287 522 389 232 456 321 233 336 340 266 315 206 369 460 394 342 339...
output:
465
result:
ok 1 number(s): "465"
Test #28:
score: 0
Accepted
time: 2ms
memory: 3512kb
input:
1000 5000 5 4 44 63 28 88 34 99 85 66 124 130 70 77 115 179 145 162 148 123 129 82 177 239 180 248 241 171 260 281 202 285 242 121 192 267 137 276 284 94 210 265 182 135 209 280 349 401 299 294 319 363 322 373 374 339 314 354 296 311 484 489 461 441 340 412 367 536 402 425 438 482 540 525 380 499 41...
output:
2721
result:
ok 1 number(s): "2721"
Test #29:
score: 0
Accepted
time: 2ms
memory: 3732kb
input:
1000 5000 31 53 14 55 22 54 21 71 59 129 40 77 78 108 80 109 87 97 121 68 119 151 146 206 126 81 236 212 257 83 105 70 165 241 144 161 170 255 153 263 155 232 123 216 370 273 234 222 278 307 237 291 147 383 180 250 374 323 435 272 296 367 378 314 404 396 283 354 347 369 337 390 446 426 517 413 456 3...
output:
2706
result:
ok 1 number(s): "2706"
Test #30:
score: 0
Accepted
time: 2ms
memory: 3532kb
input:
1000 5000 1345 166 100 56 351 297 54 637 133 324 778 106 140 152 512 69 303 222 367 313 169 517 283 556 42 352 604 96 270 528 149 234 1157 233 583 271 322 868 463 262 610 276 775 296 274 459 805 907 570 186 384 1032 385 767 1059 847 184 660 345 645 417 687 773 132 465 840 1084 897 282 387 10 698 170...
output:
2709
result:
ok 1 number(s): "2709"
Test #31:
score: 0
Accepted
time: 2ms
memory: 3588kb
input:
1000 5000 311 535 597 249 112 68 88 16 101 457 108 229 212 499 1484 358 661 32 354 252 497 223 1153 18 213 266 664 404 186 707 740 210 350 167 65 1364 103 440 955 785 629 211 704 1000 183 387 175 717 232 114 71 201 79 527 580 890 468 684 575 111 752 1742 178 55 4 138 481 583 745 420 59 361 375 926 3...
output:
2655
result:
ok 1 number(s): "2655"
Test #32:
score: 0
Accepted
time: 4ms
memory: 3720kb
input:
10000 50000 686 602 423 2818 115 448 23 790 42 162 466 549 416 623 76 126 531 164 329 177 172 756 40 190 9 132 483 541 447 5 881 318 54 282 136 21 206 317 67 116 22 744 196 338 555 100 334 245 849 851 219 1271 681 305 64 233 956 1051 764 279 86 559 2144 476 384 24 201 216 962 883 175 762 385 94 491 ...
output:
27805
result:
ok 1 number(s): "27805"
Test #33:
score: 0
Accepted
time: 2ms
memory: 3712kb
input:
10000 50000 57 198 374 279 629 542 161 71 240 358 246 571 117 220 1048 186 251 432 75 162 1130 254 817 2062 673 391 239 101 834 156 99 574 615 502 455 383 281 392 510 508 433 286 194 802 222 780 1495 1828 705 778 815 672 474 305 154 352 581 20 444 253 902 297 743 822 1503 644 40 795 866 1132 347 747...
output:
27947
result:
ok 1 number(s): "27947"
Test #34:
score: 0
Accepted
time: 4ms
memory: 3612kb
input:
10000 50000 20 26 42 43 57 61 62 70 73 80 89 105 107 116 122 127 132 158 175 176 177 179 184 188 192 198 209 211 218 228 232 240 244 256 258 264 268 273 274 282 41331 312 328 335 351 362 371 373 375 377 383 399 404 414 417 420 437 451 456 471 486 487 495 507 512 517 519 521 524 534 539 544 552 554 5...
output:
24442
result:
ok 1 number(s): "24442"
Test #35:
score: 0
Accepted
time: 4ms
memory: 3604kb
input:
10000 50000 1 2 18 21 23 24 38 47 52 58 92 96 97 98 102 117 122 129 134 144 163 171 180 189 194 197 205 211 215 218 219 222 228 234 235 246 247 250 258 265 266 268 269 271 275 283 284 285 289 296 299 302 311 313 321 323 324 330 336 342 344 358 364 369 384 388 396 397 400 406 416 421 431 433 434 438 ...
output:
8425
result:
ok 1 number(s): "8425"
Test #36:
score: 0
Accepted
time: 3ms
memory: 3648kb
input:
10000 50000 1 9 16 17 35 38 40 50 55 65 91 92 94 96 113 116 120 126 129 131 133 139 152 159 170 178 181 185 189 191 192 195 201 204 212 214 216 218 222 224 225 231 250 261 266 273 276 278 287 293 308 323 336 343 355 356 358 359 360 370 372 380 397 400 405 425 427 442 444 453 454 458 464 468 471 483 ...
output:
6864
result:
ok 1 number(s): "6864"
Test #37:
score: 0
Accepted
time: 3ms
memory: 3780kb
input:
20000 50000 2 5 10 15 16 20 21 25 26 27 33 36 38 40 42 46 50 57 65 66 67 68 69 70 75 77 78 80 83 85 86 93 94 99 102 103 106 111 112 113 114 116 118 121 126 132 135 137 139 143 144 147 150 162 163 168 170 172 173 174 176 183 185 186 187 197 201 202 204 214 220 221 227 236 239 252 256 257 263 271 277 ...
output:
12665
result:
ok 1 number(s): "12665"
Test #38:
score: 0
Accepted
time: 5ms
memory: 3972kb
input:
20000 50000 3 7 12 19 20 22 33 35 37 43 46 49 52 53 58 62 63 66 75 78 81 83 90 92 94 95 97 101 103 104 108 119 122 124 127 129 131 132 134 137 138 140 142 143 148 158 159 165 166 183 187 189 192 194 196 197 200 201 204 207 210 212 222 226 235 243 244 245 248 251 252 255 256 259 262 265 267 273 274 2...
output:
-1
result:
ok 1 number(s): "-1"
Test #39:
score: 0
Accepted
time: 5ms
memory: 3760kb
input:
20000 50000 2 5 11 24 26 27 29 31 41 43 47 50 52 61 63 64 69 71 73 75 79 86 89 92 102 109 117 118 125 131 132 135 136 139 141 143 145 149 150 151 154 160 161 167 168 169 171 172 173 176 179 183 187 189 196 204 207 220 221 222 224 225 227 229 232 233 241 242 253 254 258 260 262 266 267 272 276 278 27...
output:
17653
result:
ok 1 number(s): "17653"
Test #40:
score: 0
Accepted
time: 5ms
memory: 4216kb
input:
60000 200000 2 6 8 9 12 14 17 24 25 32 34 36 38 44 46 47 48 54 58 67 70 75 78 84 85 86 90 91 92 103 108 119 122 124 127 128 130 131 140 143 148 158 160 164 172 173 177 184 185 194 200 205 207 208 213 214 215 216 221 225 226 229 231 232 233 237 239 245 251 252 256 263 266 268 271 272 275 279 280 283 ...
output:
58675
result:
ok 1 number(s): "58675"
Test #41:
score: 0
Accepted
time: 14ms
memory: 4440kb
input:
75000 200000 1 5 12 15 16 21 22 29 37 38 51 53 55 60 66 72 74 75 80 81 89 92 93 94 96 97 100 104 105 121 122 128 130 131 133 141 147 148 150 154 157 160 163 164 166 172 179 180 188 191 196 198 201 203 205 211 212 215 216 217 229 231 232 237 239 251 257 260 263 265 270 276 277 280 283 285 287 290 295...
output:
149994
result:
ok 1 number(s): "149994"
Test #42:
score: 0
Accepted
time: 15ms
memory: 4364kb
input:
75000 200000 7 12 13 14 21 25 27 35 37 40 42 43 48 49 56 61 62 67 68 73 76 81 83 85 87 88 93 95 103 104 110 116 120 123 125 127 129 130 131 134 135 136 142 146 148 149 150 152 158 161 162 163 164 165 166 168 173 174 176 185 188 189 192 194 200 208 211 212 214 220 222 224 228 233 238 244 245 246 248 ...
output:
167190
result:
ok 1 number(s): "167190"
Test #43:
score: 0
Accepted
time: 13ms
memory: 4648kb
input:
100000 200000 6 11 16 19 20 27 30 31 34 36 38 39 50 54 56 58 59 61 73 76 79 80 81 86 88 90 94 95 98 102 105 106 107 110 111 117 118 125 135 138 144 145 154 155 158 170 171 174 176 181 185 192 195 198 203 205 209 211 214 215 219 220 224 225 228 229 230 231 234 238 240 245 246 250 251 253 254 255 259 ...
output:
114390
result:
ok 1 number(s): "114390"
Test #44:
score: 0
Accepted
time: 18ms
memory: 4732kb
input:
100000 200000 1 4 7 10 11 25 26 30 32 34 35 37 41 42 43 48 49 52 60 62 64 66 76 78 80 85 86 92 100 105 117 119 123 124 129 130 131 137 138 139 142 144 147 149 150 153 156 159 163 164 169 172 173 175 176 177 185 186 188 189 191 194 197 199 200 204 208 209 218 219 222 224 226 227 229 230 231 233 235 2...
output:
-1
result:
ok 1 number(s): "-1"
Test #45:
score: 0
Accepted
time: 12ms
memory: 4744kb
input:
100000 200000 1 10 12 13 15 21 22 23 24 26 28 29 30 35 44 45 47 48 53 54 55 56 57 60 72 73 77 83 86 87 88 95 101 106 109 111 121 130 131 132 134 135 137 139 140 141 147 151 152 155 157 160 162 163 164 165 167 170 174 176 179 181 185 188 189 193 194 196 199 204 211 216 219 222 225 227 230 237 242 244...
output:
-1
result:
ok 1 number(s): "-1"
Test #46:
score: -100
Wrong Answer
time: 12ms
memory: 4740kb
input:
100000 200000 2 3 4 5 6 7 8 10 11 14 15 21 22 24 25 26 27 29 31 37 44 45 46 47 48 50 53 56 58 63 68 74 79 84 86 89 91 98 101 102 103 104 105 109 110 114 119 123 127 129 131 132 136 138 141 144 146 150 156 157 163 165 166 168 175 176 187 188 189 191 193 197 198 199 200 202 203 205 208 210 211 212 214...
output:
56295
result:
wrong answer 1st numbers differ - expected: '87188', found: '56295'