| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 18749 |
2016-02-15T04:22:00 Z |
pichulia |
여왕벌 (KOI15_queen) |
C++ |
|
0 ms |
0 KB |
#include<stdio.h>
#include<unordered_map>
#include<unordered_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];
int p[709];
int q[709];
pair<int, pair<int, int>> b[1000000];
unordered_map<int, int> s[701];
unordered_map<int, unordered_set<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 i, j, k, l;
int si,ti;
int hi,ii;
// p = start of 1, q = start of 2
if (i0 + i1 < n)
{
p[0] = 0; q[0] = 0;
}
else if (i0 < n)
{
p[0] = 0; q[0] = n - i2;
}
else
{
p[0] = i0 - n + 1; q[0] = n - i2;
}
hi = hashing(0, p[0], q[0]);
if(s[0].count(hi)){
s[0][hi]++;
}
else
s[0][hi] = 1;
for (i = 1; i < n; i++)
{
int np, nq;
np = p[i - 1];
nq = q[i - 1];
if (i0 + i1 < (n - i))si = 2;
else if (i0 < (n - i)) si = 1;
else si = 0;
ii = hi;
hi = hashing(si, p[i-1], q[i-1]);
v[i-1][ii].insert(hi);
if(s[i].count(hi))
{
return;
}
s[i][hi] = 0;
if (si == 0)
{
if (p[i - 1]> 0) // 0 0 0 x x x
{
if (p[i - 1] != q[i - 1]) // 0 0 0 1 1 1 2 2 2
{
if (a[i][p[i - 1]][0][0][1] == 1)
{
np = p[i - 1];
if (q[i - 1] == n || a[i][q[i - 1]][1][1][2] == 2)
{
nq = q[i - 1];
}
else
nq = tel_122[i][q[i - 1]];
}
else
{
j = tel_011[i][p[i - 1]];
if (j < q[i - 1])
{
np = j;
if (q[i-1] == n || a[i][q[i - 1]][1][1][2] == 2)
{
nq = q[i - 1];
}
else
{
nq = tel_122[i][q[i - 1]];
}
}
else
{
j = q[i - 1];
// 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[i-1]];
}
else
{
if (q[i - 1] == n || a[i][q[i - 1]][0][1][2] == 2)
{
nq = q[i - 1];
np = nq;
}
else
{
nq = tel_022[i][q[i - 1]];
np = nq;
}
}
}
}
}
else // 0 0 0 2 2 2
{
if (q[i - 1] == n || a[i][q[i - 1]][0][0][2] == 2)
{
nq = q[i - 1];
np = nq;
}
else
{
nq = tel_022[i][q[i - 1]];
np = nq;
}
}
}
else if (q[i - 1] > 0) // 1 1 1 x x x
{
j = tel_011[i][0];
if (j < q[i - 1])
{
np = j;
if (q[i - 1] == n || a[i][q[i - 1]][1][1][2] == 2)
{
nq = q[i - 1];
}
else
{
nq = tel_122[i][q[i - 1]];
}
}
else
{
j = q[i - 1];
if (j < n && a[i][j][0][1][2] == 1)
{
np = j;
nq = tel_122[i][q[i-1]];
}
else
{
if (q[i - 1] == n || a[i][q[i - 1]][0][1][2] == 2)
{
nq = q[i - 1];
np = nq;
}
else
{
nq = tel_022[i][q[i - 1]];
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[i - 1] > 0) // 1 1 1 x x x
{
if (q[i - 1] == n || a[i][q[i-1]][1][1][2] == 2)
{
nq = q[i - 1];
}
else
{
nq = tel_122[i][q[i - 1]];
}
}
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[i] = np;
q[i] = nq;
}
ii = hi;
hi = hashing(0, p[n-1], q[n-1]);
v[i-1][ii].insert(hi);
s[i][hi] = 0;
}
void process2(int i0, int i1, int i2)
{
int i, j, k, l;
int si,ti;
int hi,ii;
// p = start of 1, q = start of 0
p[0] = n - i0 - i1; q[0] = n - i0;
hi = hashing(0, p[0], q[0]);
if(s[0].count(hi)){
s[0][hi]++;
}
else
s[0][hi] = 1;
for (i = 1; i < n; i++)
{
int np, nq;
np = p[i - 1];
nq = q[i - 1];
si = 2;
ii = hi;
hi = hashing(si, p[i-1], q[i-1]);
v[i-1][ii].insert(hi);
if(s[i].count(hi))
{
return;
}
s[i][hi] = 0;
if (p[i - 1]> 0) // 2 2 2 x x x
{
if (p[i - 1] != q[i - 1]) // 2 2 2 1 1 1 0 0 0
{
if (a[p[i - 1]][i][1][2][2] == 1)
{
np = p[i - 1];
if (q[i - 1] == n || a[q[i - 1]][i][0][1][1] == 0)
{
nq = q[i - 1];
}
else
nq = cel_001[q[i - 1]][i];
}
else
{
j = cel_112[p[i - 1]][i];
if (j < q[i - 1])
{
np = j;
if (q[i-1] == n || a[q[i - 1]][i][0][1][1] == 0)
{
nq = q[i - 1];
}
else
{
nq = cel_001[q[i - 1]][i];
}
}
else
{
j = q[i - 1];
// 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-1]][i];
}
else
{
if (q[i - 1] == n || a[q[i - 1]][i][0][1][2] == 0)
{
nq = q[i - 1];
np = nq;
}
else
{
nq = cel_002[q[i - 1]][i];
np = nq;
}
}
}
}
}
else // 2 2 2 0 0 0
{
if (q[i - 1] == n || a[q[i - 1]][i][0][2][2] == 0)
{
nq = q[i - 1];
np = nq;
}
else
{
nq = cel_002[q[i - 1]][i];
np = nq;
}
}
}
else if (q[i - 1] > 0) // 1 1 1 x x x
{
j = cel_112[0][i];
if (j < q[i - 1])
{
np = j;
if (q[i - 1] == n || a[q[i - 1]][i][0][1][1] == 0)
{
nq = q[i - 1];
}
else
{
nq = cel_001[q[i - 1]][i];
}
}
else
{
j = q[i - 1];
if (j < n && a[j][i][0][1][2] == 1)
{
np = j;
nq = cel_001[q[i-1]][i];
}
else
{
if (q[i - 1] == n || a[q[i - 1]][i][0][1][2] == 0)
{
nq = q[i - 1];
np = nq;
}
else
{
nq = cel_002[q[i - 1]][i];
np = nq;
}
}
}
}
else // 0 0 0 ...
{
nq = cel_002[0][i];
np = nq;
}
p[i] = np;
q[i] = nq;
}
ii = hi;
hi = hashing(0, p[n-1], q[n-1]);
v[i-1][ii].insert(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;
{
for(i=0; i<m; i++)
{
scanf("%d %d %d", &b[i].first, &b[i].second.first, &b[i].second.second);
}
sort(b,b+m);
for(i=0;i<m;)
{
for(l=0; l<=n;l++)
{
s[l].clear();
v[l].clear();
}
for(j=i+1;j<m;j++)
if(b[i].first != b[j].first)
break;
if(b[i].second.second>=n)
{
for(k=i+1; k<j; k++)
{
if(b[k].second.second < n)
break;
}
ccnt += k - i;
for(l=k-1; l>=i; l--)
{
process2(b[l].first, b[l].second.first, b[l].second.second);
}
i=k;
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(l=0; l<=n;l++)
{
s[l].clear();
v[l].clear();
}
}
for(k=i;k<j;k++)
{
process(b[k].first, b[k].second.first, b[k].second.second);
}
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 (i = 0; i < n; i++)
{
for (j = 1; j < n; j++)
{
r[i][j] += r[i][j-1];
}
c[0][i] += ccnt * 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);
}
}
Compilation message
In file included from /usr/include/c++/4.9/unordered_map:35:0,
from queen.cpp:2:
/usr/include/c++/4.9/bits/c++0x_warning.h:32:2: error: #error This file requires compiler and library support for the ISO C++ 2011 standard. This support is currently experimental, and must be enabled with the -std=c++11 or -std=gnu++11 compiler options.
#error This file requires compiler and library support for the \
^
queen.cpp:20:24: error: ‘>>’ should be ‘> >’ within a nested template argument list
pair<int, pair<int, int>> b[1000000];
^
queen.cpp:22:1: error: ‘unordered_map’ does not name a type
unordered_map<int, int> s[701];
^
queen.cpp:23:1: error: ‘unordered_map’ does not name a type
unordered_map<int, unordered_set<int>> v[701];
^
queen.cpp: In function ‘void process(int, int, int)’:
queen.cpp:48:5: error: ‘s’ was not declared in this scope
if(s[0].count(hi)){
^
queen.cpp:66:3: error: ‘v’ was not declared in this scope
v[i-1][ii].insert(hi);
^
queen.cpp:67:6: error: ‘s’ was not declared in this scope
if(s[i].count(hi))
^
queen.cpp:71:3: error: ‘s’ was not declared in this scope
s[i][hi] = 0;
^
queen.cpp:219:2: error: ‘v’ was not declared in this scope
v[i-1][ii].insert(hi);
^
queen.cpp:220:2: error: ‘s’ was not declared in this scope
s[i][hi] = 0;
^
queen.cpp:31:12: warning: unused variable ‘k’ [-Wunused-variable]
int i, j, k, l;
^
queen.cpp:31:15: warning: unused variable ‘l’ [-Wunused-variable]
int i, j, k, l;
^
queen.cpp:32:9: warning: unused variable ‘ti’ [-Wunused-variable]
int si,ti;
^
queen.cpp: In function ‘void process2(int, int, int)’:
queen.cpp:230:5: error: ‘s’ was not declared in this scope
if(s[0].count(hi)){
^
queen.cpp:245:3: error: ‘v’ was not declared in this scope
v[i-1][ii].insert(hi);
^
queen.cpp:246:6: error: ‘s’ was not declared in this scope
if(s[i].count(hi))
^
queen.cpp:250:3: error: ‘s’ was not declared in this scope
s[i][hi] = 0;
^
queen.cpp:371:2: error: ‘v’ was not declared in this scope
v[i-1][ii].insert(hi);
^
queen.cpp:372:2: error: ‘s’ was not declared in this scope
s[i][hi] = 0;
^
queen.cpp:224:12: warning: unused variable ‘k’ [-Wunused-variable]
int i, j, k, l;
^
queen.cpp:224:15: warning: unused variable ‘l’ [-Wunused-variable]
int i, j, k, l;
^
queen.cpp:225:9: warning: unused variable ‘ti’ [-Wunused-variable]
int si,ti;
^
queen.cpp: In function ‘int main()’:
queen.cpp:494:17: warning: array subscript has type ‘char’ [-Wchar-subscripts]
a[i][j][ii][jj][kk] = cc;
^
queen.cpp:494:21: warning: array subscript has type ‘char’ [-Wchar-subscripts]
a[i][j][ii][jj][kk] = cc;
^
queen.cpp:494:25: warning: array subscript has type ‘char’ [-Wchar-subscripts]
a[i][j][ii][jj][kk] = cc;
^
queen.cpp:509:5: error: ‘s’ was not declared in this scope
s[l].clear();
^
queen.cpp:510:5: error: ‘v’ was not declared in this scope
v[l].clear();
^
queen.cpp:530:10: warning: ‘auto’ changes meaning in C++11; please remove it [-Wc++0x-compat]
for(auto x : s[l])
^
queen.cpp:530:15: error: ‘x’ does not name a type
for(auto x : s[l])
^
queen.cpp:546:5: error: expected ‘;’ before ‘}’ token
}
^
queen.cpp:546:5: error: expected primary-expression before ‘}’ token
queen.cpp:546:5: error: expected ‘;’ before ‘}’ token
queen.cpp:546:5: error: expected primary-expression before ‘}’ token
queen.cpp:546:5: error: expected ‘)’ before ‘}’ token
queen.cpp:546:5: error: expected primary-expression before ‘}’ token
queen.cpp:549:6: error: ‘s’ was not declared in this scope
s[l].clear();
^
queen.cpp:550:6: error: ‘v’ was not declared in this scope
v[l].clear();
^
queen.cpp:560:9: warning: ‘auto’ changes meaning in C++11; please remove it [-Wc++0x-compat]
for(auto x : s[j])
^
queen.cpp:560:14: error: ‘x’ does not name a type
for(auto x : s[j])
^
queen.cpp:576:4: error: expected ‘;’ before ‘}’ token
}
^
queen.cpp:576:4: error: expected primary-expression before ‘}’ token
queen.cpp:576:4: error: expected ‘;’ before ‘}’ token
queen.cpp:576:4: error: expected primary-expression before ‘}’ token
queen.cpp:576:4: error: expected ‘)’ before ‘}’ token
queen.cpp:576:4: error: expected primary-expression before ‘}’ token
queen.cpp:470:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
^
queen.cpp:475:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", x);
^
queen.cpp:502:75: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &b[i].first, &b[i].second.first, &b[i].second.second);
^
