Submission #1870399
Source Code Expand
#include <cstdio>
typedef long long ll ;
#define rep(i, a, b) for (int i = a; i <= b; ++ i)
const int f[4][2] = {{0, 0}, {1, 0}, {1, 1}, {0, 1}}, w[4] = {1, - 1, 1, - 1}, N = 2e6 + 10, mo = 1e9 + 7 ;
using namespace std ;
int a[6][2], fac[N], inv[N] ;
void upd(int &x, int y) { x = (x + y) % mo ; }
int C(int x, int y) { return (ll) fac[x + y] * inv[x] % mo * inv[y] % mo ; }
int mul(int a, int b) {
int ans = 1, w = a % mo ;
for ( ; b; b /= 2) {
if (b & 1) ans = (ll) ans * w % mo ;
w = (ll) w * w % mo ;
}
return ans ;
}
int calc(int xa, int ya, int xc, int yc) {
int res = 0 ;
rep(i, a[2][0], a[3][0])
upd(res, (ll) C(i - xa, a[2][1] - 1 - ya) * C(xc - i, yc - a[2][1]) % mo * (- i - a[2][1]) % mo) ,
upd(res, (ll) C(i - xa, a[3][1] - ya) * C(xc - i, yc - a[3][1] - 1) % mo * (i + 1 + a[3][1]) % mo) ;
rep(i, a[2][1], a[3][1])
upd(res, (ll) C(a[2][0] - 1 - xa, i - ya) * C(xc - a[2][0], yc - i) % mo * (- i - a[2][0]) % mo) ,
upd(res, (ll) C(a[3][0] - xa, i - ya) * C(xc - a[3][0] - 1, yc - i) % mo * (i + 1 + a[3][0]) % mo) ;
return res ;
}
int main() {
fac[0] = inv[0] = 1 ;
rep(i, 1, N - 5) fac[i] = (ll) fac[i - 1] * i % mo ;
inv[N - 5] = mul(fac[N - 5], mo - 2) ;
for (int i = N - 6 ; i > 0 ; -- i) inv[i] = (ll) inv[i + 1] * (i + 1) % mo ;
rep(i, 0, 1) rep(j, 0, 5) scanf("%d", &a[j][i]) ;
rep(i, 0, 1) rep(j, 0, 1) -- a[j][i] ;
int ans = 0 ;
rep(i, 0, 3) rep(j, 0, 3)
upd(ans, calc(a[f[i][0]][0] + f[i][0], a[f[i][1]][1] + f[i][1], a[4 + f[j][0]][0] + f[j][0], a[4 + f[j][1]][1] + f[j][1]) * w[i] * w[j]) ;
printf("%d\n", (ans + mo) % mo) ;
return 0 ;
}
Submission Info
Submission Time |
|
Task |
E - Sightseeing Plan |
User |
mjy0724 |
Language |
C++14 (GCC 5.4.1) |
Score |
1600 |
Code Size |
1637 Byte |
Status |
AC |
Exec Time |
943 ms |
Memory |
15872 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:32:50: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
rep(i, 0, 1) rep(j, 0, 5) scanf("%d", &a[j][i]) ;
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1600 / 1600 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
29 ms |
15744 KB |
sample_02.txt |
AC |
28 ms |
15744 KB |
sample_03.txt |
AC |
159 ms |
15744 KB |
subtask_1_01.txt |
AC |
28 ms |
15744 KB |
subtask_1_02.txt |
AC |
69 ms |
15744 KB |
subtask_1_03.txt |
AC |
614 ms |
15744 KB |
subtask_1_04.txt |
AC |
153 ms |
15744 KB |
subtask_1_05.txt |
AC |
454 ms |
15744 KB |
subtask_1_06.txt |
AC |
93 ms |
15744 KB |
subtask_1_07.txt |
AC |
215 ms |
15744 KB |
subtask_1_08.txt |
AC |
175 ms |
15744 KB |
subtask_1_09.txt |
AC |
165 ms |
15744 KB |
subtask_1_10.txt |
AC |
160 ms |
15744 KB |
subtask_1_11.txt |
AC |
163 ms |
15744 KB |
subtask_1_12.txt |
AC |
28 ms |
15744 KB |
subtask_1_13.txt |
AC |
76 ms |
15744 KB |
subtask_1_14.txt |
AC |
28 ms |
15744 KB |
subtask_1_15.txt |
AC |
28 ms |
15744 KB |
subtask_1_16.txt |
AC |
111 ms |
15744 KB |
subtask_1_17.txt |
AC |
70 ms |
15872 KB |
subtask_1_18.txt |
AC |
94 ms |
15744 KB |
subtask_1_19.txt |
AC |
28 ms |
15744 KB |
subtask_1_20.txt |
AC |
943 ms |
15744 KB |
subtask_1_21.txt |
AC |
29 ms |
15744 KB |
subtask_1_22.txt |
AC |
654 ms |
15744 KB |
subtask_1_23.txt |
AC |
843 ms |
15744 KB |
subtask_1_24.txt |
AC |
678 ms |
15744 KB |