QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #411063 | #6663. 회의실 2 | bachbeo2007 | 3 | 60ms | 57440kb | C++20 | 2.3kb | 2024-05-14 21:03:14 | 2024-05-14 21:03:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2005;
const int mod = 1e9+7;
#define pii pair<int,int>
#define fi first
#define se second
int power(int a,int n){
int res=1;
while(n){
if(n&1) res=1LL*res*a%mod;
a=1LL*a*a%mod;n>>=1;
}
return res;
}
int fac[maxn],dfac[maxn];
void combi(int N){
fac[0]=1;
for(int i=1;i<=N;i++) fac[i]=1LL*fac[i-1]*i%mod;
dfac[N]=power(fac[N],mod-2);
for(int i=N;i>=1;i--) dfac[i-1]=1LL*dfac[i]*i%mod;
//cout << dfac[2] << '\n';
}
int rt[2*maxn],num[maxn];
int cnt[2*maxn][2*maxn],dp[2*maxn][2*maxn];
vector<int> lt[2*maxn];
int count_removals(std::vector<int> S, std::vector<int> E){
int N = S.size();combi(N);
for(int i=0;i<N;i++){
cnt[S[i]][E[i]]++;
rt[S[i]]=max(rt[S[i]],E[i]);
lt[E[i]].push_back(S[i]);
}
for(int l=2*N;l>=1;l--) for(int r=l+1;r<=2*N;r++) cnt[l][r]+=cnt[l+1][r]+cnt[l][r-1]-cnt[l+1][r-1];
int cc=0,mx=0;
vector<pii> p;
for(int i=1;i<=2*N;i++){
if(mx<i){
if(cnt[cc][mx]) p.push_back({cc,mx});
cc=mx=i;
}
mx=max(mx,rt[i]);
}
if(cnt[cc][mx]) p.push_back({cc,mx});
int res=1;
for(auto [L,R]:p){
num[cnt[L][R]]++;
//cout << L << ' ' << R << ' ' << cnt[L][R] << '\n';
vector<pii> range;
for(int i=L;i<=R;i++) for(int j:lt[i]){
range.push_back({j,i});
dp[j][i]=1LL*fac[N-1]*dfac[N-cnt[j][i]]%mod;
}
for(int len=1;len<=R-L;len++){
for(int l=L;l<=R-len+1;l++){
int r=l+len-1;
if(!dp[l][r]) continue;
//cout << '*' << l << ' ' << r << ' ' << dp[l][r] << '\n';
for(auto [cl,cr]:range){
if(cl>r || cr<l || (l<=cl && cr<=r)) continue;
//cout << cl << ' ' << cr << '\n';
cl=min(cl,l);cr=max(cr,r);
//cout << N-cnt[l][r]-1 << ' ' << N-cnt[cl][cr] << ' ' << 1LL*fac[N-cnt[l][r]-1]*dfac[N-cnt[cl][cr]]%mod << '\n';
dp[cl][cr]=(dp[cl][cr]+1LL*dp[l][r]*fac[N-cnt[l][r]-1]%mod*dfac[N-cnt[cl][cr]]%mod)%mod;
}
}
}
res=1LL*res*dp[L][R]%mod;
}
for(int i=1;i<=N;i++) res=1LL*res*fac[num[i]]%mod;
return res;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 3
Accepted
Test #1:
score: 3
Accepted
time: 1ms
memory: 3728kb
input:
2 1 4 2 3
output:
Meeting 2 - By moonrabbit2 My answer is: 2
result:
ok 2 lines
Test #2:
score: 3
Accepted
time: 1ms
memory: 3872kb
input:
10 1 20 2 9 3 4 5 8 6 7 10 17 11 16 12 13 14 15 18 19
output:
Meeting 2 - By moonrabbit2 My answer is: 845040
result:
ok 2 lines
Test #3:
score: 3
Accepted
time: 1ms
memory: 3856kb
input:
10 1 20 2 11 3 12 4 13 5 14 6 15 7 16 8 17 9 18 10 19
output:
Meeting 2 - By moonrabbit2 My answer is: 3628800
result:
ok 2 lines
Test #4:
score: 3
Accepted
time: 1ms
memory: 3788kb
input:
4 1 2 3 4 5 6 7 8
output:
Meeting 2 - By moonrabbit2 My answer is: 24
result:
ok 2 lines
Test #5:
score: 3
Accepted
time: 1ms
memory: 3724kb
input:
2 1 2 3 4
output:
Meeting 2 - By moonrabbit2 My answer is: 2
result:
ok 2 lines
Test #6:
score: 3
Accepted
time: 1ms
memory: 3764kb
input:
2 1 3 2 4
output:
Meeting 2 - By moonrabbit2 My answer is: 2
result:
ok 2 lines
Test #7:
score: 3
Accepted
time: 1ms
memory: 3892kb
input:
10 1 5 2 3 4 7 6 11 8 9 10 15 12 13 14 20 16 17 18 19
output:
Meeting 2 - By moonrabbit2 My answer is: 13280
result:
ok 2 lines
Test #8:
score: 3
Accepted
time: 0ms
memory: 3828kb
input:
10 1 5 2 9 3 10 4 12 6 14 7 16 8 17 11 18 13 19 15 20
output:
Meeting 2 - By moonrabbit2 My answer is: 1797408
result:
ok 2 lines
Test #9:
score: 3
Accepted
time: 1ms
memory: 4100kb
input:
10 12 16 5 7 10 19 2 3 4 6 17 20 8 11 1 15 14 18 9 13
output:
Meeting 2 - By moonrabbit2 My answer is: 647760
result:
ok 2 lines
Test #10:
score: 3
Accepted
time: 1ms
memory: 3824kb
input:
10 1 20 6 11 7 17 12 19 3 16 10 18 4 8 5 15 2 13 9 14
output:
Meeting 2 - By moonrabbit2 My answer is: 3261600
result:
ok 2 lines
Test #11:
score: 3
Accepted
time: 1ms
memory: 3836kb
input:
10 1 20 11 18 6 14 8 13 7 19 12 16 10 17 5 15 3 9 2 4
output:
Meeting 2 - By moonrabbit2 My answer is: 2193120
result:
ok 2 lines
Test #12:
score: 3
Accepted
time: 1ms
memory: 3824kb
input:
10 1 20 14 15 3 18 4 8 10 16 12 19 2 11 5 7 9 13 6 17
output:
Meeting 2 - By moonrabbit2 My answer is: 2490480
result:
ok 2 lines
Test #13:
score: 3
Accepted
time: 1ms
memory: 4072kb
input:
10 1 20 2 16 10 18 3 11 5 19 9 17 6 7 13 14 4 15 8 12
output:
Meeting 2 - By moonrabbit2 My answer is: 3054720
result:
ok 2 lines
Test #14:
score: 3
Accepted
time: 1ms
memory: 4104kb
input:
10 1 20 2 8 5 9 13 16 4 12 14 15 11 18 7 17 3 19 6 10
output:
Meeting 2 - By moonrabbit2 My answer is: 2432160
result:
ok 2 lines
Test #15:
score: 3
Accepted
time: 1ms
memory: 3800kb
input:
10 1 20 5 16 3 4 6 9 12 15 2 17 18 19 8 10 13 14 7 11
output:
Meeting 2 - By moonrabbit2 My answer is: 1242900
result:
ok 2 lines
Test #16:
score: 3
Accepted
time: 1ms
memory: 4076kb
input:
10 1 20 8 15 10 19 11 17 5 13 6 9 12 18 2 3 7 14 4 16
output:
Meeting 2 - By moonrabbit2 My answer is: 1716480
result:
ok 2 lines
Test #17:
score: 3
Accepted
time: 1ms
memory: 3892kb
input:
10 1 20 4 5 2 3 15 17 8 9 7 19 6 13 14 16 10 18 11 12
output:
Meeting 2 - By moonrabbit2 My answer is: 1035760
result:
ok 2 lines
Test #18:
score: 3
Accepted
time: 1ms
memory: 3896kb
input:
10 1 20 13 16 18 19 2 3 8 10 12 17 4 5 9 11 6 7 14 15
output:
Meeting 2 - By moonrabbit2 My answer is: 770400
result:
ok 2 lines
Test #19:
score: 3
Accepted
time: 1ms
memory: 4088kb
input:
9 1 18 4 6 12 17 7 9 14 15 11 13 10 16 5 8 2 3
output:
Meeting 2 - By moonrabbit2 My answer is: 94080
result:
ok 2 lines
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #20:
score: 8
Accepted
time: 1ms
memory: 3984kb
input:
20 31 32 7 8 39 40 25 26 19 20 21 22 9 10 17 18 1 2 23 24 15 16 29 30 5 6 35 36 3 4 11 12 33 34 27 28 13 14 37 38
output:
Meeting 2 - By moonrabbit2 My answer is: 146326063
result:
ok 2 lines
Test #21:
score: 8
Accepted
time: 0ms
memory: 3972kb
input:
20 22 23 4 5 6 7 32 33 18 19 1 40 38 39 24 25 30 31 34 35 26 27 14 15 28 29 12 13 16 17 2 3 10 11 8 9 36 37 20 21
output:
Meeting 2 - By moonrabbit2 My answer is: 114632607
result:
ok 2 lines
Test #22:
score: 8
Accepted
time: 1ms
memory: 3916kb
input:
20 24 27 18 21 20 23 6 9 16 19 36 39 8 11 26 29 14 17 22 25 12 15 1 3 32 35 34 37 4 7 30 33 2 5 38 40 28 31 10 13
output:
Meeting 2 - By moonrabbit2 My answer is: 524288
result:
ok 2 lines
Test #23:
score: 8
Accepted
time: 1ms
memory: 4224kb
input:
20 4 9 30 40 20 23 36 37 2 3 1 5 14 19 10 15 28 29 16 17 22 25 32 33 6 7 12 13 8 11 24 31 18 21 26 27 34 35 38 39
output:
Meeting 2 - By moonrabbit2 My answer is: 135122973
result:
ok 2 lines
Test #24:
score: 8
Accepted
time: 1ms
memory: 4056kb
input:
20 3 28 25 26 7 10 20 27 2 35 22 23 29 30 17 18 8 9 15 16 36 37 11 14 4 19 1 40 12 13 31 32 5 6 33 34 38 39 21 24
output:
Meeting 2 - By moonrabbit2 My answer is: 498214363
result:
ok 2 lines
Test #25:
score: 8
Accepted
time: 1ms
memory: 3976kb
input:
20 4 7 27 28 33 36 1 40 3 8 37 38 12 13 22 23 25 26 20 29 34 35 9 16 2 19 30 39 21 24 10 15 17 18 31 32 5 6 11 14
output:
Meeting 2 - By moonrabbit2 My answer is: 644114283
result:
ok 2 lines
Test #26:
score: 8
Accepted
time: 1ms
memory: 3980kb
input:
20 13 28 20 21 3 38 5 36 7 34 14 27 12 29 17 24 2 39 9 32 6 35 16 25 15 26 4 37 18 23 19 22 1 40 11 30 10 31 8 33
output:
Meeting 2 - By moonrabbit2 My answer is: 146326063
result:
ok 2 lines
Test #27:
score: 8
Accepted
time: 1ms
memory: 3948kb
input:
20 7 26 2 16 15 34 14 33 10 30 9 29 4 19 23 37 17 35 13 32 12 31 6 22 1 11 25 39 3 18 24 38 20 36 8 27 28 40 5 21
output:
Meeting 2 - By moonrabbit2 My answer is: 322126540
result:
ok 2 lines
Test #28:
score: 8
Accepted
time: 1ms
memory: 3920kb
input:
20 5 21 13 33 15 34 9 26 8 25 19 36 18 35 7 23 2 16 31 40 30 39 12 32 11 28 3 17 29 38 10 27 4 20 6 22 24 37 1 14
output:
Meeting 2 - By moonrabbit2 My answer is: 469150957
result:
ok 2 lines
Test #29:
score: 8
Accepted
time: 1ms
memory: 3948kb
input:
20 5 19 7 24 26 38 33 40 6 22 8 25 4 15 14 30 29 39 16 31 2 11 17 32 21 36 18 34 9 27 3 12 13 28 20 35 1 10 23 37
output:
Meeting 2 - By moonrabbit2 My answer is: 859543975
result:
ok 2 lines
Test #30:
score: 8
Accepted
time: 1ms
memory: 4052kb
input:
20 11 26 34 40 33 39 30 38 1 4 2 13 25 36 3 16 12 28 15 31 10 24 14 29 7 20 27 37 5 17 9 23 18 32 22 35 6 19 8 21
output:
Meeting 2 - By moonrabbit2 My answer is: 659775882
result:
ok 2 lines
Test #31:
score: 0
Wrong Answer
time: 0ms
memory: 4016kb
input:
20 18 31 10 20 8 17 4 12 14 22 11 21 24 33 9 19 25 34 1 2 6 13 23 32 26 36 16 29 7 15 28 38 3 5 30 39 35 40 27 37
output:
Meeting 2 - By moonrabbit2 My answer is: 380169074
result:
wrong answer 2nd lines differ - expected: 'My answer is: 308501386', found: 'My answer is: 380169074'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #96:
score: 12
Accepted
time: 15ms
memory: 57188kb
input:
2000 2245 2246 2189 2190 1681 1682 1005 1006 1367 1368 2797 2798 2407 2408 1511 1512 1441 1442 3795 3796 1835 1836 1747 1748 2941 2942 3435 3436 2095 2096 1631 1632 2737 2738 1653 1654 2637 2638 3823 3824 3491 3492 15 16 325 326 2195 2196 3037 3038 3039 3040 1431 1432 3241 3242 715 716 2909 2910 119...
output:
Meeting 2 - By moonrabbit2 My answer is: 100292593
result:
ok 2 lines
Test #97:
score: 12
Accepted
time: 54ms
memory: 57168kb
input:
2000 3104 3105 2562 2563 2094 2095 2492 2493 3126 3127 2616 2617 464 465 1036 1037 3668 3669 3326 3327 324 325 1428 1429 3586 3587 3312 3313 1222 1223 720 721 3738 3739 2404 2405 3538 3539 2040 2041 1590 1591 3362 3363 3302 3303 3994 3995 804 805 1930 1931 3110 3111 2402 2403 2888 2889 1360 1361 378...
output:
Meeting 2 - By moonrabbit2 My answer is: 201100294
result:
ok 2 lines
Test #98:
score: 0
Wrong Answer
time: 19ms
memory: 57260kb
input:
2000 908 909 1288 1289 3958 3959 2244 2245 2628 2629 3644 3645 3010 3011 3344 3345 2318 2319 624 625 2738 2739 3754 3755 912 913 2072 2073 3372 3373 3050 3051 1814 1815 3806 3807 2432 2433 3558 3559 2830 2831 3054 3055 2650 2651 1252 1253 728 729 76 77 2444 2445 1298 1299 130 131 3708 3709 2134 2135...
output:
Meeting 2 - By moonrabbit2 My answer is: 372732414
result:
wrong answer 2nd lines differ - expected: 'My answer is: 752846731', found: 'My answer is: 372732414'
Subtask #5:
score: 0
Wrong Answer
Test #120:
score: 12
Accepted
time: 25ms
memory: 41524kb
input:
1557 1352 1357 3085 3086 7 154 2861 2866 131 134 14 105 327 338 759 778 357 358 1863 1864 1968 1969 2795 2808 64 71 1299 1300 1215 1216 2048 2053 1750 1751 1957 1958 2598 2599 1817 1822 2699 2722 2583 2588 2005 2100 1334 1335 356 359 882 883 1707 1708 3001 3002 818 821 1102 1103 2968 2969 2788 2789 ...
output:
Meeting 2 - By moonrabbit2 My answer is: 869729098
result:
ok 2 lines
Test #121:
score: 12
Accepted
time: 60ms
memory: 57432kb
input:
2000 724 737 2049 2050 1296 1307 324 325 2467 2468 3547 3558 2448 2449 1383 1388 1430 1431 1425 1434 1997 2902 585 606 3942 3943 1727 1728 1438 1439 3034 3035 1427 1432 3909 3912 2579 2580 2015 2018 100 103 1527 1528 1325 1326 1268 1271 2255 2256 2089 2092 2440 2441 2513 2514 175 176 494 505 1019 10...
output:
Meeting 2 - By moonrabbit2 My answer is: 428355024
result:
ok 2 lines
Test #122:
score: 12
Accepted
time: 49ms
memory: 57412kb
input:
2000 1712 1713 1952 1953 3600 3609 2397 2402 2131 2132 2368 2455 1839 1842 1297 1298 1021 1024 3778 3781 41 42 309 310 3987 3990 3185 3186 2535 2536 3719 3724 1526 1563 3302 3303 3177 3182 908 909 1245 1260 2470 2475 736 737 3428 3429 1422 1423 3804 3805 1782 1787 2627 2628 1012 1013 2669 2672 1987 ...
output:
Meeting 2 - By moonrabbit2 My answer is: 708869468
result:
ok 2 lines
Test #123:
score: 12
Accepted
time: 52ms
memory: 57132kb
input:
2000 1016 1019 914 915 2694 2697 207 210 2585 2606 1266 1267 3479 3480 1208 1209 1317 1320 192 211 131 150 3738 3739 1138 1141 216 221 946 949 1397 1398 3202 3207 1535 1536 3067 3068 487 510 3347 3386 2935 2940 2566 2571 1934 1939 3152 3153 710 743 1059 1086 2928 2929 564 571 1053 1054 2381 2388 104...
output:
Meeting 2 - By moonrabbit2 My answer is: 824552202
result:
ok 2 lines
Test #124:
score: 12
Accepted
time: 54ms
memory: 57276kb
input:
2000 2202 2207 2717 2718 2173 2182 1466 1489 3515 3518 3863 3864 492 495 378 385 3182 3185 2081 2082 76 79 1186 1191 722 723 95 96 3595 3596 2415 2416 2392 2393 3486 3489 146 151 3292 3439 2637 2638 1182 1183 750 753 2327 2330 2165 2220 2210 2211 435 448 904 907 2340 2341 483 484 1451 1454 3504 3505...
output:
Meeting 2 - By moonrabbit2 My answer is: 71166676
result:
ok 2 lines
Test #125:
score: 12
Accepted
time: 55ms
memory: 57440kb
input:
2000 3153 3156 3388 3389 486 503 924 929 553 560 1706 1707 3421 3422 853 854 571 576 2470 2475 2773 2774 3492 3495 3863 3866 1017 1028 2060 2061 2348 2349 1679 1684 2039 2064 2267 2270 3700 3723 3711 3712 3963 3964 2548 2563 444 457 878 879 3475 3478 3229 3230 961 964 2340 2341 3444 3449 1915 1918 3...
output:
Meeting 2 - By moonrabbit2 My answer is: 223729049
result:
ok 2 lines
Test #126:
score: 0
Wrong Answer
time: 11ms
memory: 57392kb
input:
2000 1140 1141 775 776 3703 3754 231 232 3182 3183 624 625 806 807 1964 1965 839 850 1290 1293 2635 2636 3311 3408 1251 1256 1644 1645 489 492 3972 3973 925 990 74 77 1802 1803 2231 2240 2026 2027 841 842 2935 2936 2028 2029 2141 2144 3629 3630 1860 1861 1530 1531 2018 2365 108 109 3720 3721 2159 21...
output:
Meeting 2 - By moonrabbit2 My answer is: 706502555
result:
wrong answer 2nd lines differ - expected: 'My answer is: 289813993', found: 'My answer is: 706502555'
Subtask #6:
score: 0
Time Limit Exceeded
Test #143:
score: 0
Time Limit Exceeded
input:
1342 2401 2667 982 2071 494 1558 420 1442 91 681 1002 2088 1268 2277 971 2064 1092 2156 1980 2591 1081 2144 131 852 1011 2091 157 924 1551 2438 1940 2579 477 1530 1902 2569 1245 2261 448 1487 138 883 1511 2415 616 1712 492 1556 1225 2245 476 1529 1077 2140 804 1923 137 882 1387 2342 1222 2243 1824 2...
output:
Unauthorized output
result:
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%