#include<stdio.h>
#include<unordered_map>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
int m, n;
char a[701][701][3][3][3];
int tel_011[701][701];
int tel_022[701][701];
int tel_122[701][701];
int cel_001[701][701];
int cel_002[701][701];
int cel_112[701][701];
int r[701][701];
int c[701][701];
char x[999];
vector<pair<int, pair<int, int>>> b1;
vector<pair<int, pair<int, int>>> b2;
vector<pair<int, pair<int, int>>> b3;
int m1, m2, m3;
unordered_map<int, int> s[701];
unordered_map<int, vector<int>> v[701];
__inline int hashing(int si, int p, int q)
{
return (si<<20)|(p<<10)|q;
}
void process(int i0, int i1, int i2, int aaa)
{
int i, j, k, l;
int si,ti;
int hi,ii;
int p,q;
// p = start of 1, q = start of 2
if (i0 + i1 < n)
{
p = 0; q = 0;
}
else if (i0 < n)
{
p = 0; q = n - i2;
}
else
{
p = i0 - n + 1; q = n - i2;
}
hi = hashing(0, p, q);
if(s[0].count(hi)){
s[0][hi]+=aaa;
return;
}
else
s[0][hi] = aaa;
for (i = 1; i < n; ++i)
{
int np, nq;
np = p;
nq = q;
if (i0 + i1 < (n - i))si = 2;
else if (i0 < (n - i)) si = 1;
else si = 0;
ii = hi;
hi = hashing(si, p, q);
v[i-1][ii].push_back(hi);
if(s[i].count(hi))
{
return;
}
s[i][hi] = 0;
if (si == 0)
{
if (p> 0) // 0 0 0 x x x
{
if (p != q) // 0 0 0 1 1 1 2 2 2
{
if (a[i][p][0][0][1] == 1)
{
np = p;
if (q == n || a[i][q][1][1][2] == 2)
{
nq = q;
}
else
nq = tel_122[i][q];
}
else
{
j = tel_011[i][p];
if (j < q)
{
np = j;
if (q == n || a[i][q][1][1][2] == 2)
{
nq = q;
}
else
{
nq = tel_122[i][q];
}
}
else
{
j = q;
// 0 0 1 1 2 2
// 0 0 0 0 ?
if (j < n && a[i][j][0][1][2] == 1)
{
np = j;
nq = tel_122[i][q];
}
else
{
if (q == n || a[i][q][0][1][2] == 2)
{
nq = q;
np = nq;
}
else
{
nq = tel_022[i][q];
np = nq;
}
}
}
}
}
else // 0 0 0 2 2 2
{
if (q == n || a[i][q][0][0][2] == 2)
{
nq = q;
np = nq;
}
else
{
nq = tel_022[i][q];
np = nq;
}
}
}
else if (q > 0) // 1 1 1 x x x
{
j = tel_011[i][0];
if (j < q)
{
np = j;
if (q == n || a[i][q][1][1][2] == 2)
{
nq = q;
}
else
{
nq = tel_122[i][q];
}
}
else
{
j = q;
if (j < n && a[i][j][0][1][2] == 1)
{
np = j;
nq = tel_122[i][q];
}
else
{
if (q == n || a[i][q][0][1][2] == 2)
{
nq = q;
np = nq;
}
else
{
nq = tel_022[i][q];
np = nq;
}
}
}
}
else // 2 2 2 ...
{
nq = tel_022[i][0];
np = nq;
}
} // end of si == 0
else if (si == 1)
{
np = 0;
if (q > 0) // 1 1 1 x x x
{
if (q == n || a[i][q][1][1][2] == 2)
{
nq = q;
}
else
{
nq = tel_122[i][q];
}
}
else // 2 2 2 x x x
{
nq = tel_122[i][0];
}
} // end of si == 1
else
{
np = nq = 0;
} // end of si == 2
p = np;
q = nq;
}
ii = hi;
hi = hashing(0, p, q);
v[i-1][ii].push_back(hi);
s[i][hi] = 0;
}
void process3(int i0, int i1, int i2, int aaa)
{
int i, j, k, l;
int si,ti;
int hi,ii;
int p,q;
// p = start of 1, q = start of 2
p = i0 - n + 1; q = n - i2;
hi = hashing(0, p, q);
if(s[0].count(hi)){
s[0][hi]+=aaa;
return;
}
else
s[0][hi] = aaa;
for (i = 1; i < n; ++i)
{
int np, nq;
np = p;
nq = q;
si = 0;
ii = hi;
hi = hashing(si, p, q);
v[i-1][ii].push_back(hi);
if(s[i].count(hi))
{
return;
}
s[i][hi] = 0;
if (p> 0) // 0 0 0 x x x
{
if (p != q) // 0 0 0 1 1 1 2 2 2
{
if (a[i][p][0][0][1] == 1)
{
np = p;
if (q == n || a[i][q][1][1][2] == 2)
{
nq = q;
}
else
nq = tel_122[i][q];
}
else
{
j = tel_011[i][p];
if (j < q)
{
np = j;
if (q == n || a[i][q][1][1][2] == 2)
{
nq = q;
}
else
{
nq = tel_122[i][q];
}
}
else
{
j = q;
// 0 0 1 1 2 2
// 0 0 0 0 ?
if (j < n && a[i][j][0][1][2] == 1)
{
np = j;
nq = tel_122[i][q];
}
else
{
if (q == n || a[i][q][0][1][2] == 2)
{
nq = q;
np = nq;
}
else
{
nq = tel_022[i][q];
np = nq;
}
}
}
}
}
else // 0 0 0 2 2 2
{
if (q == n || a[i][q][0][0][2] == 2)
{
nq = q;
np = nq;
}
else
{
nq = tel_022[i][q];
np = nq;
}
}
}
else if (q > 0) // 1 1 1 x x x
{
j = tel_011[i][0];
if (j < q)
{
np = j;
if (q == n || a[i][q][1][1][2] == 2)
{
nq = q;
}
else
{
nq = tel_122[i][q];
}
}
else
{
j = q;
if (j < n && a[i][j][0][1][2] == 1)
{
np = j;
nq = tel_122[i][q];
}
else
{
if (q == n || a[i][q][0][1][2] == 2)
{
nq = q;
np = nq;
}
else
{
nq = tel_022[i][q];
np = nq;
}
}
}
}
else // 2 2 2 ...
{
nq = tel_022[i][0];
np = nq;
}
p = np;
q = nq;
}
ii = hi;
hi = hashing(0, p, q);
v[i-1][ii].push_back(hi);
s[i][hi] = 0;
}
void process2(int i0, int i1, int i2,int aaa)
{
int i, j, k, l;
int si,ti;
int hi,ii;
int p,q;
// p = start of 1, q = start of 0
p = n - i0 - i1; q = n - i0;
hi = hashing(0, p, q);
if(s[0].count(hi)){
s[0][hi]+=aaa;
return;
}
else
s[0][hi] = aaa;
for (i = 1; i < n; ++i)
{
int np, nq;
np = p;
nq = q;
si = 2;
ii = hi;
hi = hashing(si, p, q);
v[i-1][ii].push_back(hi);
if(s[i].count(hi))
{
return;
}
s[i][hi] = 0;
if (p> 0) // 2 2 2 x x x
{
if (p != q) // 2 2 2 1 1 1 0 0 0
{
if (a[p][i][1][2][2] == 1)
{
np = p;
if (q == n || a[q][i][0][1][1] == 0)
{
nq = q;
}
else
nq = cel_001[q][i];
}
else
{
j = cel_112[p][i];
if (j < q)
{
np = j;
if (q == n || a[q][i][0][1][1] == 0)
{
nq = q;
}
else
{
nq = cel_001[q][i];
}
}
else
{
j = q;
// 2 2 1 1 0 0
// 2 2 2 2 ?
if (j < n && a[j][i][0][1][2] == 1)
{
np = j;
nq = cel_001[q][i];
}
else
{
if (q == n || a[q][i][0][1][2] == 0)
{
nq = q;
np = nq;
}
else
{
nq = cel_002[q][i];
np = nq;
}
}
}
}
}
else // 2 2 2 0 0 0
{
if (q == n || a[q][i][0][2][2] == 0)
{
nq = q;
np = nq;
}
else
{
nq = cel_002[q][i];
np = nq;
}
}
}
else if (q > 0) // 1 1 1 x x x
{
j = cel_112[0][i];
if (j < q)
{
np = j;
if (q == n || a[q][i][0][1][1] == 0)
{
nq = q;
}
else
{
nq = cel_001[q][i];
}
}
else
{
j = q;
if (j < n && a[j][i][0][1][2] == 1)
{
np = j;
nq = cel_001[q][i];
}
else
{
if (q == n || a[q][i][0][1][2] == 0)
{
nq = q;
np = nq;
}
else
{
nq = cel_002[q][i];
np = nq;
}
}
}
}
else // 0 0 0 ...
{
nq = cel_002[0][i];
np = nq;
}
p = np;
q = nq;
}
ii = hi;
hi = hashing(0, p, q);
v[i-1][ii].push_back(hi);
s[i][hi] = 0;
}
void precess()
{
int i, j, k, l;
for (i = 1; i < n; ++i)
{
for (j = 0; j < n;)
{
for (k = j+1; k < n; ++k)
{
if (a[i][k][0][1][1] == 1)
break;
}
for (l = j; l < k; ++l)
{
tel_011[i][l] = k;
}
j = k;
}
for (j = 0; j < n;)
{
for (k = j+1; k < n; ++k)
{
if (a[i][k][0][2][2] == 2)
break;
}
for (l = j; l < k; ++l)
{
tel_022[i][l] = k;
}
j = k;
}
for (j = 0; j < n;)
{
for (k = j+1; k < n; ++k)
{
if (a[i][k][1][2][2] == 2)
break;
}
for (l = j; l < k; ++l)
{
tel_122[i][l] = k;
}
j = k;
}
tel_011[i][n] = n;
tel_022[i][n] = n;
tel_122[i][n] = n;
}
for (i = 1; i < n; ++i)
{
for (j = 0; j < n;)
{
for (k = j+1; k < n; ++k)
{
if (a[k][i][0][0][1] == 0)
break;
}
for (l = j; l < k; ++l)
{
cel_001[l][i] = k;
}
j = k;
}
for (j = 0; j < n;)
{
for (k = j+1; k < n; ++k)
{
if (a[k][i][0][0][2] == 0)
break;
}
for (l = j; l < k; ++l)
{
cel_002[l][i] = k;
}
j = k;
}
for (j = 0; j < n;)
{
for (k = j+1; k < n; ++k)
{
if (a[k][i][1][1][2] == 1)
break;
}
for (l = j; l < k; ++l)
{
cel_112[l][i] = k;
}
j = k;
}
cel_001[n][i] = n;
cel_002[n][i] = n;
cel_112[n][i] = n;
}
}
int main()
{
scanf("%d %d", &n, &m);
int i, j, k, l;
for (i = 1; i < n; ++i)
for (j = 1; j < n; ++j)
{
scanf("%s", x);
k = 0;
for (char ii = 0; ii < 3; ++ii)
for (char jj = 0; jj < 3; ++jj)
for (char kk = 0; kk < 3; ++kk)
{
char cc = x[k++];
if (cc == 'L')
{
cc = ii;
}
else if (cc == 'D')
{
cc = jj;
}
else
{
cc = kk;
}
a[i][j][ii][jj][kk] = cc;
}
}
precess();
int ccnt = 0;
{
m1=m2=0;
for(i=0; i<m; ++i)
{
int i0, i1, i2;
scanf("%d %d %d", &i0, &i1, &i2);
if(i2>=n-1)
{
b2.push_back(pair<int, pair<int, int>>(i0, pair<int, int>(i1, i2)));
m2++;
}
else if (i0 >= n-1)
{
b3.push_back(pair<int, pair<int, int>>(i0, pair<int, int>(i1, i2)));
m3++;
}
else
{
b1.push_back(pair<int, pair<int, int>>(i0, pair<int, int>(i1, i2)));
m1++;
}
}
sort(b1.begin(), b1.end());
sort(b2.begin(),b2.end());
sort(b3.begin(),b3.end());
for(i=0;i<m1;)
{
for(l=0; l<=n;++l)
{
s[l].clear();
v[l].clear();
}
for(j=i+1;j<m1;++j)
if(b1[i].first != b1[j].first)
break;
for(k=i;k<j;)
{
for(l=k+1; l<j; ++l)
{
if(b1[k] != b1[l])
break;
}
process(b1[k].first, b1[k].second.first, b1[k].second.second, l-k);
k=l;
}
i = j;
for(j=0;j<=n;++j)
{
for(auto x : s[j])
{
int xi = x.first;
int xp = (xi&(0xffc00))>>10;
int xq = xi&(0x3ff);
// printf("%d %d %d %d\n",j, xp, xq, x.second);
if(j>0)
{
r[j-1][xp]+=x.second;
r[j-1][xq]+=x.second;
}
for(auto y : v[j][xi])
{
s[j+1][y]+=x.second;
}
}
}
}
int em2 = sqrt(m2) + 1;
int em3 = sqrt(m3) + 1;
for(j=0; j<m3; j+=em3)
{
for(l=0; l<=n;++l)
{
s[l].clear();
v[l].clear();
}
int ee = min(m3, em3+j);
for(i=j; i<ee;)
{
for(l=i+1; l<ee; ++l)
{
if(b3[i] != b3[l])
break;
}
process3(b3[i].first, b3[i].second.first, b3[i].second.second, l-i);
i=l;
}
for(l=0;l<=n;++l)
{
for(auto x : s[l])
{
int xi = x.first;
int xp = (xi&(0xffc00))>>10;
int xq = xi&(0x3ff);
// printf("%d %d %d %d\n",j, xp, xq, x.second);
if(l>0)
{
r[l-1][xp]+=x.second;
r[l-1][xq]+=x.second;
}
for(auto y : v[l][xi])
{
s[l+1][y]+=x.second;
}
}
}
}
for(j=0; j<m2; j+=em2)
{
for(l=0; l<=n;++l)
{
s[l].clear();
v[l].clear();
}
int ee = min(m2, em2+j);
for(i=j; i<ee;)
{
for(l=i+1; l<ee; ++l)
{
if(b2[i] != b2[l])
break;
}
process2(b2[i].first, b2[i].second.first, b2[i].second.second, l-i);
i=l;
}
for(l=0;l<=n;++l)
{
for(auto x : s[l])
{
int xi = x.first;
int xp = (xi&(0xffc00))>>10;
int xq = xi&(0x3ff);
// printf("%d %d %d %d\n",j, xp, xq, x.second);
if(l>0)
{
c[xp][l-1]-=x.second;
c[xq][l-1]-=x.second;
}
for(auto y : v[l][xi])
{
s[l+1][y]+=x.second;
}
}
}
}
for (i = 0; i < n; ++i)
{
for (j = 1; j < n; ++j)
{
r[i][j] += r[i][j-1];
}
c[0][i] += m2 * 2;
for(j=1; j<n; ++j)
{
c[j][i] += c[j-1][i];
}
}
for(i=0; i<n; ++i, printf("\n"))
for(j=0; j<n; ++j)
printf("%d ",r[i][j] + c[i][j] + 1);
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
30144 KB |
Output is correct |
| 2 |
Correct |
0 ms |
30144 KB |
Output is correct |
| 3 |
Correct |
0 ms |
30144 KB |
Output is correct |
| 4 |
Correct |
0 ms |
30144 KB |
Output is correct |
| 5 |
Correct |
42 ms |
30144 KB |
Output is correct |
| 6 |
Correct |
40 ms |
30144 KB |
Output is correct |
| 7 |
Correct |
29 ms |
30144 KB |
Output is correct |
| 8 |
Correct |
109 ms |
30144 KB |
Output is correct |
| 9 |
Correct |
85 ms |
30144 KB |
Output is correct |
| 10 |
Correct |
106 ms |
30144 KB |
Output is correct |
| 11 |
Correct |
277 ms |
30144 KB |
Output is correct |
| 12 |
Correct |
271 ms |
30144 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
30368 KB |
Output is correct |
| 2 |
Correct |
83 ms |
30368 KB |
Output is correct |
| 3 |
Correct |
145 ms |
30600 KB |
Output is correct |
| 4 |
Correct |
431 ms |
30500 KB |
Output is correct |
| 5 |
Correct |
333 ms |
30436 KB |
Output is correct |
| 6 |
Correct |
422 ms |
30452 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
30288 KB |
Output is correct |
| 2 |
Correct |
56 ms |
30564 KB |
Output is correct |
| 3 |
Correct |
224 ms |
30716 KB |
Output is correct |
| 4 |
Correct |
1484 ms |
32408 KB |
Output is correct |
| 5 |
Correct |
1347 ms |
31884 KB |
Output is correct |
| 6 |
Correct |
1350 ms |
31760 KB |
Output is correct |
| 7 |
Correct |
1400 ms |
32668 KB |
Output is correct |
| 8 |
Correct |
1690 ms |
33864 KB |
Output is correct |
| 9 |
Correct |
1553 ms |
33224 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4374 ms |
45512 KB |
Output is correct |
| 2 |
Execution timed out |
5000 ms |
47884 KB |
Program timed out |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
30144 KB |
Output is correct |
| 2 |
Correct |
0 ms |
30144 KB |
Output is correct |
| 3 |
Correct |
0 ms |
30144 KB |
Output is correct |
| 4 |
Correct |
0 ms |
30144 KB |
Output is correct |
| 5 |
Correct |
370 ms |
54344 KB |
Output is correct |
| 6 |
Correct |
344 ms |
54748 KB |
Output is correct |
| 7 |
Correct |
364 ms |
51656 KB |
Output is correct |
| 8 |
Correct |
342 ms |
51656 KB |
Output is correct |
| 9 |
Execution timed out |
5000 ms |
71744 KB |
Program timed out |
| 10 |
Halted |
0 ms |
0 KB |
- |
