Submission #18776

#TimeUsernameProblemLanguageResultExecution timeMemory
18776pichulia여왕벌 (KOI15_queen)C++14
68 / 100
5000 ms524288 KiB
#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; } } } } { for(l=0; l<=n;++l) { s[l].clear(); v[l].clear(); } for(i=0; i<m3;) { for(l=i+1; l<m3; ++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(l=0; l<=n;++l) { s[l].clear(); v[l].clear(); } for(i=0; i<m2;) { for(l=i+1; l<m2; ++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); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...