QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #21649 | #2848. 城市地铁规划 | gsh# | WA | 4ms | 3712kb | C++20 | 2.2kb | 2022-03-07 18:09:40 | 2022-05-08 03:46:52 |
Judging History
answer
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<cmath>
#include<ctime>
#include<bitset>
#include<vector>
#include<cstdio>
#include<string>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
#define mkp make_pair
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define fs fflush(stdout)
#define ump unordered_map
#define pq priority_queue
#define clz __builtin_clz
#define ctz __builtin_ctz
#define space putchar(' ')
#define enter putchar('\n')
#define sz(x) (int)x.size()
#define np next_permutation
#define clzl __builtin_clzll
#define par __builtin_parity
#define ctzl __builtin_ctzll
#define ppc __builtin_popcount
#define parl __builtin_parityll
#define all(x) x.begin(),x.end()
#define ppcl __builtin_popcountll
#define ms(x,y) memset(x,y,sizeof(x))
#define debug(x) cerr<<#x<<"= "<<(x)<<'\n'
template<class T> inline T &read(T &x){
x=0;int f=1;char ch=getchar();
while(ch<48||ch>57){if(ch=='-') f=-f;ch=getchar();}
while(ch>=48&&ch<=57) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*=f;
}
template<class T> inline void print(T x){
static char buf[40];static int cnt=0;
if(x<0) putchar(45),x=-x;
do buf[++cnt]=x%10^48;while(x/=10);
do putchar(buf[cnt--]);while(cnt);
}
#define mod 59393
#define inf 0x3f3f3f3f
#define fpi freopen("","r",stdin)
#define fpo freopen("","w",stdout)
int a[11],sum[3005],deg[3005],dp[6005],lst[6005];
int main(){
int n=read(n),k=read(k),i,j,now=n-2;
for(i=0;i<=k;i++) read(a[i]);
for(i=1;i<n;i++){int mul=1;for(j=0;j<=k;j++) (sum[i]+=a[j]*mul)%=mod,(mul*=i)%=mod;}
print(n-1),space,dp[0]=n*sum[1];
for(i=2;i<=n;i++) for(j=i-1;j<n-1;j++) if(dp[j-i+1]+sum[i]-sum[1]>dp[j]) dp[j]=dp[j-i+1]+sum[i]-sum[1],lst[j]=j-i+1;
print(dp[n-2]),enter;
for(i=1;i<=n;i++) deg[i]=now-lst[now]+1,now=lst[now];
sort(deg+1,deg+n+1),now=n+1;
for(i=1;i<=n;i++) if(deg[i]>1){now=i;break;}
for(i=1;i<n-1;i++){
print(i),space,print(now),enter;
deg[now]--;if(deg[now]==1) now++;
}print(n-1),space,print(n);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 3700kb
input:
63 7 4 50 14 48 33 13 44 24
output:
62 992106 1 33 2 34 3 34 4 35 5 35 6 36 7 36 8 37 9 37 10 38 11 38 12 39 13 39 14 40 15 40 16 41 17 41 18 42 19 42 20 43 21 43 22 44 23 44 24 45 25 45 26 46 27 46 28 47 29 47 30 48 31 48 32 49 33 49 34 50 35 50 36 51 37 51 38 52 39 52 40 53 41 53 42 54 43 54 44 55 45 55 46 56 47 56 48 57 49 57 50 58...
result:
ok
Test #2:
score: 0
Accepted
time: 2ms
memory: 3584kb
input:
208 7 23 28 14 16 46 28 26 28
output:
207 3317121 1 106 2 106 3 107 4 107 5 108 6 108 7 109 8 109 9 110 10 110 11 111 12 111 13 112 14 112 15 113 16 113 17 114 18 114 19 115 20 115 21 116 22 116 23 117 24 117 25 118 26 118 27 119 28 119 29 120 30 120 31 121 32 121 33 122 34 122 35 123 36 123 37 124 38 124 39 125 40 125 41 126 42 126 43 ...
result:
ok
Test #3:
score: 0
Accepted
time: 4ms
memory: 3620kb
input:
2928 3 27 20 7 29
output:
2927 13889888 1 2663 2 2663 3 2663 4 2663 5 2663 6 2663 7 2663 8 2663 9 2663 10 2663 11 2663 12 2664 13 2664 14 2664 15 2664 16 2664 17 2664 18 2664 19 2664 20 2664 21 2664 22 2664 23 2665 24 2665 25 2665 26 2665 27 2665 28 2665 29 2665 30 2665 31 2665 32 2665 33 2665 34 2666 35 2666 36 2666 37 2666...
result:
ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
320 3 46 42 15 15
output:
319 1260206 1 298 2 298 3 298 4 298 5 298 6 298 7 298 8 298 9 298 10 298 11 299 12 299 13 299 14 299 15 299 16 299 17 299 18 299 19 299 20 299 21 299 22 299 23 299 24 299 25 300 26 300 27 300 28 300 29 300 30 300 31 300 32 300 33 300 34 300 35 300 36 300 37 300 38 300 39 301 40 301 41 301 42 301 43 ...
result:
ok
Test #5:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
380 5 41 27 8 3 31 0
output:
379 3140470 1 305 2 305 3 305 4 306 5 306 6 306 7 306 8 306 9 307 10 307 11 307 12 307 13 307 14 308 15 308 16 308 17 308 18 308 19 309 20 309 21 309 22 309 23 309 24 310 25 310 26 310 27 310 28 310 29 311 30 311 31 311 32 311 33 311 34 312 35 312 36 312 37 312 38 312 39 313 40 313 41 313 42 313 43 ...
result:
ok
Test #6:
score: 0
Accepted
time: 3ms
memory: 3612kb
input:
365 5 35 20 24 29 3 25
output:
364 3508667 1 245 2 245 3 245 4 246 5 246 6 246 7 247 8 247 9 247 10 248 11 248 12 248 13 249 14 249 15 249 16 250 17 250 18 250 19 251 20 251 21 251 22 252 23 252 24 252 25 253 26 253 27 253 28 254 29 254 30 254 31 255 32 255 33 255 34 256 35 256 36 256 37 257 38 257 39 257 40 258 41 258 42 258 43 ...
result:
ok
Test #7:
score: 0
Accepted
time: 3ms
memory: 3600kb
input:
318 6 4 44 46 6 37 14 49
output:
317 6799456 1 161 2 161 3 162 4 162 5 163 6 163 7 164 8 164 9 165 10 165 11 166 12 166 13 167 14 167 15 168 16 168 17 169 18 169 19 170 20 170 21 171 22 171 23 172 24 172 25 173 26 173 27 174 28 174 29 175 30 175 31 176 32 176 33 177 34 177 35 178 36 178 37 179 38 179 39 180 40 180 41 181 42 181 43 ...
result:
ok
Test #8:
score: 0
Accepted
time: 3ms
memory: 3588kb
input:
416 6 30 23 4 16 45 32 19
output:
415 5383994 1 210 2 210 3 211 4 211 5 212 6 212 7 213 8 213 9 214 10 214 11 215 12 215 13 216 14 216 15 217 16 217 17 218 18 218 19 219 20 219 21 220 22 220 23 221 24 221 25 222 26 222 27 223 28 223 29 224 30 224 31 225 32 225 33 226 34 226 35 227 36 227 37 228 38 228 39 229 40 229 41 230 42 230 43 ...
result:
ok
Test #9:
score: 0
Accepted
time: 3ms
memory: 3616kb
input:
572 5 15 27 5 18 3 46
output:
571 9396678 1 383 2 383 3 383 4 384 5 384 6 384 7 385 8 385 9 385 10 386 11 386 12 386 13 387 14 387 15 387 16 388 17 388 18 388 19 389 20 389 21 389 22 390 23 390 24 390 25 391 26 391 27 391 28 392 29 392 30 392 31 393 32 393 33 393 34 394 35 394 36 394 37 395 38 395 39 395 40 396 41 396 42 396 43 ...
result:
ok
Test #10:
score: 0
Accepted
time: 3ms
memory: 3572kb
input:
531 8 20 13 35 27 41 43 36 25 5
output:
530 9024252 1 355 2 356 3 356 4 356 5 357 6 357 7 357 8 358 9 358 10 358 11 359 12 359 13 359 14 360 15 360 16 360 17 361 18 361 19 361 20 362 21 362 22 362 23 363 24 363 25 363 26 364 27 364 28 364 29 365 30 365 31 365 32 366 33 366 34 366 35 367 36 367 37 367 38 368 39 368 40 368 41 369 42 369 43 ...
result:
ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
487 10 29 29 40 45 5 16 40 47 47 2 14
output:
486 18026623 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 51 ...
result:
ok
Test #12:
score: 0
Accepted
time: 2ms
memory: 3616kb
input:
584 7 10 27 29 8 32 43 26 3
output:
583 11437238 1 294 2 294 3 295 4 295 5 296 6 296 7 297 8 297 9 298 10 298 11 299 12 299 13 300 14 300 15 301 16 301 17 302 18 302 19 303 20 303 21 304 22 304 23 305 24 305 25 306 26 306 27 307 28 307 29 308 30 308 31 309 32 309 33 310 34 310 35 311 36 311 37 312 38 312 39 313 40 313 41 314 42 314 43...
result:
ok
Test #13:
score: 0
Accepted
time: 3ms
memory: 3556kb
input:
59 4 48 16 9 42 21
output:
58 422967 1 49 2 49 3 49 4 49 5 49 6 50 7 50 8 50 9 50 10 50 11 51 12 51 13 51 14 51 15 51 16 52 17 52 18 52 19 52 20 52 21 53 22 53 23 53 24 53 25 53 26 54 27 54 28 54 29 54 30 54 31 55 32 55 33 55 34 55 35 55 36 56 37 56 38 56 39 56 40 56 41 57 42 57 43 57 44 57 45 57 46 58 47 58 48 58 49 58 50 58...
result:
ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
561 3 22 31 17 49
output:
560 3223790 1 499 2 500 3 500 4 500 5 500 6 500 7 500 8 500 9 500 10 500 11 501 12 501 13 501 14 501 15 501 16 501 17 501 18 501 19 501 20 502 21 502 22 502 23 502 24 502 25 502 26 502 27 502 28 502 29 503 30 503 31 503 32 503 33 503 34 503 35 503 36 503 37 503 38 504 39 504 40 504 41 504 42 504 43 ...
result:
ok
Test #15:
score: 0
Accepted
time: 3ms
memory: 3552kb
input:
629 6 26 31 41 32 13 39 41
output:
628 13149156 1 316 2 317 3 317 4 318 5 318 6 319 7 319 8 320 9 320 10 321 11 321 12 322 13 322 14 323 15 323 16 324 17 324 18 325 19 325 20 326 21 326 22 327 23 327 24 328 25 328 26 329 27 329 28 330 29 330 30 331 31 331 32 332 33 332 34 333 35 333 36 334 37 334 38 335 39 335 40 336 41 336 42 337 43...
result:
ok
Test #16:
score: 0
Accepted
time: 2ms
memory: 3484kb
input:
616 3 38 48 27 2
output:
615 1394108 1 592 2 592 3 592 4 592 5 592 6 592 7 592 8 592 9 592 10 592 11 592 12 592 13 592 14 592 15 593 16 593 17 593 18 593 19 593 20 593 21 593 22 593 23 593 24 593 25 593 26 593 27 593 28 593 29 593 30 593 31 593 32 593 33 593 34 593 35 593 36 593 37 593 38 593 39 593 40 594 41 594 42 594 43 ...
result:
ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
744 2 49 45 50
output:
743 1425426 1 722 2 722 3 722 4 722 5 722 6 722 7 722 8 722 9 722 10 722 11 722 12 722 13 722 14 722 15 722 16 722 17 723 18 723 19 723 20 723 21 723 22 723 23 723 24 723 25 723 26 723 27 723 28 723 29 723 30 723 31 723 32 723 33 723 34 723 35 723 36 723 37 723 38 723 39 723 40 723 41 723 42 723 43 ...
result:
ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
629 7 27 18 48 24 37 38 6 3
output:
628 9258317 1 472 2 473 3 473 4 474 5 474 6 474 7 474 8 475 9 475 10 475 11 475 12 476 13 476 14 476 15 476 16 477 17 477 18 477 19 477 20 478 21 478 22 478 23 478 24 479 25 479 26 479 27 479 28 480 29 480 30 480 31 480 32 481 33 481 34 481 35 481 36 482 37 482 38 482 39 482 40 483 41 483 42 483 43 ...
result:
ok
Test #19:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
602 8 17 25 14 13 2 16 23 24 44
output:
601 9947756 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 51 5...
result:
ok
Test #20:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
900 2 9 13 12
output:
899 787522 1 887 2 887 3 887 4 887 5 887 6 887 7 887 8 887 9 887 10 887 11 887 12 887 13 887 14 887 15 888 16 888 17 888 18 888 19 888 20 888 21 888 22 888 23 888 24 888 25 888 26 888 27 888 28 888 29 888 30 888 31 888 32 888 33 888 34 888 35 888 36 888 37 888 38 888 39 888 40 888 41 888 42 888 43 8...
result:
ok
Test #21:
score: 0
Accepted
time: 3ms
memory: 3560kb
input:
839 7 12 12 28 33 35 29 14 17
output:
838 24516016 1 421 2 422 3 422 4 423 5 423 6 424 7 424 8 425 9 425 10 426 11 426 12 427 13 427 14 428 15 428 16 429 17 429 18 430 19 430 20 431 21 431 22 432 23 432 24 433 25 433 26 434 27 434 28 435 29 435 30 436 31 436 32 437 33 437 34 438 35 438 36 439 37 439 38 440 39 440 40 441 41 441 42 442 43...
result:
ok
Test #22:
score: 0
Accepted
time: 3ms
memory: 3620kb
input:
768 7 27 3 40 6 39 9 48 31
output:
767 18960055 1 386 2 386 3 387 4 387 5 388 6 388 7 389 8 389 9 390 10 390 11 391 12 391 13 392 14 392 15 393 16 393 17 394 18 394 19 395 20 395 21 396 22 396 23 397 24 397 25 398 26 398 27 399 28 399 29 400 30 400 31 401 32 401 33 402 34 402 35 403 36 403 37 404 38 404 39 405 40 405 41 406 42 406 43...
result:
ok
Test #23:
score: 0
Accepted
time: 3ms
memory: 3548kb
input:
783 3 25 19 31 45
output:
782 4263811 1 697 2 697 3 697 4 697 5 697 6 697 7 697 8 698 9 698 10 698 11 698 12 698 13 698 14 698 15 698 16 698 17 699 18 699 19 699 20 699 21 699 22 699 23 699 24 699 25 699 26 700 27 700 28 700 29 700 30 700 31 700 32 700 33 700 34 700 35 701 36 701 37 701 38 701 39 701 40 701 41 701 42 701 43 ...
result:
ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
2 4 24 9 31 45 15
output:
1 248 1 2
result:
ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
792 5 28 40 21 32 44 11
output:
791 6695732 1 529 2 530 3 530 4 530 5 531 6 531 7 531 8 532 9 532 10 532 11 533 12 533 13 533 14 534 15 534 16 534 17 535 18 535 19 535 20 536 21 536 22 536 23 537 24 537 25 537 26 538 27 538 28 538 29 539 30 539 31 539 32 540 33 540 34 540 35 541 36 541 37 541 38 542 39 542 40 542 41 543 42 543 43 ...
result:
ok
Test #26:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
939 5 35 7 31 40 25 28
output:
938 12031060 1 628 2 628 3 628 4 629 5 629 6 629 7 630 8 630 9 630 10 631 11 631 12 631 13 632 14 632 15 632 16 633 17 633 18 633 19 634 20 634 21 634 22 635 23 635 24 635 25 636 26 636 27 636 28 637 29 637 30 637 31 638 32 638 33 638 34 639 35 639 36 639 37 640 38 640 39 640 40 641 41 641 42 641 43...
result:
ok
Test #27:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
924 6 30 26 21 8 12 42 26
output:
923 14203740 1 464 2 464 3 465 4 465 5 466 6 466 7 467 8 467 9 468 10 468 11 469 12 469 13 470 14 470 15 471 16 471 17 472 18 472 19 473 20 473 21 474 22 474 23 475 24 475 25 476 26 476 27 477 28 477 29 478 30 478 31 479 32 479 33 480 34 480 35 481 36 481 37 482 38 482 39 483 40 483 41 484 42 484 43...
result:
ok
Test #28:
score: 0
Accepted
time: 3ms
memory: 3616kb
input:
902 8 8 48 35 25 32 28 21 2 44
output:
901 13244886 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 51 ...
result:
ok
Test #29:
score: 0
Accepted
time: 3ms
memory: 3600kb
input:
1021 2 11 16 14
output:
1020 977447 1 1005 2 1005 3 1005 4 1005 5 1005 6 1005 7 1005 8 1005 9 1005 10 1005 11 1005 12 1006 13 1006 14 1006 15 1006 16 1006 17 1006 18 1006 19 1006 20 1006 21 1006 22 1006 23 1006 24 1006 25 1006 26 1006 27 1006 28 1006 29 1006 30 1006 31 1006 32 1006 33 1006 34 1006 35 1006 36 1006 37 1006 3...
result:
ok
Test #30:
score: -100
Wrong Answer
time: 3ms
memory: 3672kb
input:
1 9 18 7 32 20 44 12 15 38 14 43
output:
0 0 0 1
result:
wrong answer