Submission #00358

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
#define mod 1000000007
ll add(ll x, ll y){
return (x+y)%mod;
}
ll mul(ll x, ll y){
return (x%mod)*(y%mod)%mod;
}
ll powll(ll x, ll y){
ll res = 1LL;
while(y){
if (y & 1LL)
res *= x;
res %= mod;
x = (x*x) % mod;
y >>= 1LL;
}
return res;
}
ll divll(ll x, ll y){
return (x * powll(y,mod-2)) % mod;
}
VVL mulmat(VVL &A, VVL &B){
int n = A.size();
VVL C(n, VL(n));
REP(i,n) REP(j,n) REP(k,n) (C[i][j] += A[i][k] * B[k][j]) %= mod;
return C;
}
VVL powmat(VVL &A, ll x){
int n = A.size();
VVL B(n, VL(n));
REP(i,n) B[i][i] = 1;
while (x) {
if (x & 1) B = mulmat(B, A);
A = mulmat(A, A);
x >>= 1;
}
return B;
}
int main() {
ll w, h, t;
scanf("%lld %lld %lld", &w, &h, &t);
VVI a(w, VI(h));
int m;
cin >> m;
while (m--){
int x, y;
scanf("%d %d", &x, &y);
a[x-1][y-1] = 1;
}
ll n = w * h;
int di[] = {1,-1,0,0}, dj[] = {0,0,1,-1};
VVL A(n, VL(n));
REP(i,w) REP(j,h){
if (a[i][j]) continue;
REP(k,4){
int ii = i + di[k], jj = j + dj[k];
if (ii < 0 || jj < 0 || ii >= w || jj >= h || a[ii][jj]) continue;
A[i + w * j][ii + w * jj] = 1;
}
}
A = mulmat(A, A);
// REP(i,n){
// REP(j,n){
// cout << A[i][j];
// }
// cout << endl;
// }
ll ww = (w+1)/2;
ll n1 = ww * h, n2 = n1;
VVL A1(n1, VL(n1)), A2(n2, VL(n2));
int ddi[] = {-2,-1,-1,0,0,0,1,1,2}, ddj[] = {0,-1,1,-2,0,2,-1,1,0};
REP(i,w) REP(j,h){
REP(k,9){
int ii = i + ddi[k], jj = j + ddj[k];
if (ii < 0 || jj < 0 || ii >= w || jj >= w) continue;
if ((i + j) % 2 == 0){
A1[i/2 + ww * j][ii/2 + ww * jj] = A[i + w * j][ii + w * jj];
}else{
A2[i/2 + ww * j][ii/2 + ww * jj] = A[i + w * j][ii + w * jj];
}
}
}
// REP(i,n1){
// REP(j,n1){
// cout << A1[i][j];
// }
// cout << endl;
// }
t /= 2;
A1 = powmat(A1, t);
A2 = powmat(A2, t);
int q;
cin >> q;
while (q--){
int si, sj, gi, gj;
scanf("%d %d %d %d", &si, &sj, &gi, &gj);
si--;
sj--;
gi--;
gj--;
if ((abs(si-gi) + abs(sj-gj)) % 2) printf("0\n");
else if ((si + sj) % 2 == 0) printf("%lld\n", A1[si/2 + ww * sj][gi/2 + ww * gj]);
else printf("%lld\n", A2[si/2 + ww * sj][gi/2 + ww * gj]);
}
return 0;
}

ステータス

項目 データ
問題 0005 - devilswalk
ユーザー名 TangentDay
投稿日時 2017-07-07 22:58:43
言語 C++11
状態 Wrong Answer
得点 0
ソースコード長 3327 Byte
最大実行時間 455 ms
最大メモリ使用量 1944 KB

セット

セット 得点 Cases
1 ALL 0 / 100 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
00_sample_01.in AC 16 ms 480 KB
1
02_random_01.in WA 12 ms 584 KB
1
02_random_02.in RE 100 ms 548 KB
1
02_random_03.in RE 27 ms 632 KB
1
02_random_04.in WA 18 ms 588 KB
1
02_random_05.in RE 24 ms 496 KB
1
02_random_06.in WA 16 ms 580 KB
1
02_random_07.in RE 25 ms 776 KB
1
02_random_08.in RE 23 ms 556 KB
1
02_random_09.in RE 18 ms 640 KB
1
02_random_10.in WA 23 ms 724 KB
1
02_random_11.in RE 21 ms 732 KB
1
02_random_12.in RE 22 ms 668 KB
1
02_random_13.in RE 19 ms 644 KB
1
02_random_14.in WA 19 ms 468 KB
1
02_random_15.in RE 20 ms 556 KB
1
02_random_16.in RE 21 ms 572 KB
1
02_random_17.in WA 20 ms 656 KB
1
02_random_18.in WA 19 ms 740 KB
1
02_random_19.in RE 23 ms 760 KB
1
02_random_20.in WA 39 ms 800 KB
1
02_random_21.in AC 34 ms 824 KB
1
02_random_22.in WA 27 ms 752 KB
1
02_random_23.in RE 18 ms 852 KB
1
02_random_24.in WA 12 ms 816 KB
1
02_random_25.in WA 21 ms 916 KB
1
02_random_26.in RE 26 ms 856 KB
1
02_random_27.in RE 31 ms 956 KB
1
02_random_28.in RE 20 ms 740 KB
1
02_random_29.in WA 21 ms 836 KB
1
02_random_30.in WA 14 ms 740 KB
1
03_large_01.in RE 62 ms 1608 KB
1
03_large_02.in RE 59 ms 1540 KB
1
03_large_03.in AC 453 ms 1856 KB
1
03_large_04.in WA 455 ms 1928 KB
1
03_large_05.in WA 259 ms 1680 KB
1
03_large_06.in RE 64 ms 1708 KB
1
03_large_07.in AC 442 ms 1896 KB
1
03_large_08.in RE 69 ms 1708 KB
1
03_large_09.in WA 405 ms 1944 KB
1
03_large_10.in RE 71 ms 1940 KB
1