답안 #18766

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18766 2016-02-15T05:05:10 Z pichulia 여왕벌 (KOI15_queen) C++14
68 / 100
5000 ms 74844 KB
#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];
int p[709];
int q[709];
vector<pair<int, pair<int, int>>> b1;
vector<pair<int, pair<int, int>>> b2;
int m1, m2;


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;
	// 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]+=aaa;
	}
	else
		s[0][hi] = aaa;
	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].push_back(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].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;
	// 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]+=aaa;
		return;
	}
	else
		s[0][hi] = aaa;
	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].push_back(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].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
			{
				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());
		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;
      em2 = (int)(sqrt(m2))+1;
  //    em2 = m2 / 5 + 1;
		for(j=0; j<m2; j+=em2)
		{
			for(l=0; l<=n;l++)
			{
				s[l].clear();
				v[l].clear();
			}
			for(i=j; i<m2 && i<j+em2;)
			{
				for(l=i+1; l<m2 && l<j+em2; 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 26 ms 30144 KB Output is correct
6 Correct 38 ms 30144 KB Output is correct
7 Correct 34 ms 30144 KB Output is correct
8 Correct 48 ms 30144 KB Output is correct
9 Correct 87 ms 30144 KB Output is correct
10 Correct 212 ms 30144 KB Output is correct
11 Correct 267 ms 30144 KB Output is correct
12 Correct 264 ms 30144 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 30528 KB Output is correct
2 Correct 97 ms 30528 KB Output is correct
3 Correct 172 ms 30528 KB Output is correct
4 Correct 548 ms 30528 KB Output is correct
5 Correct 456 ms 30528 KB Output is correct
6 Correct 519 ms 30528 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 30336 KB Output is correct
2 Correct 52 ms 30468 KB Output is correct
3 Correct 341 ms 30600 KB Output is correct
4 Correct 1644 ms 31920 KB Output is correct
5 Correct 1510 ms 31788 KB Output is correct
6 Correct 1536 ms 31788 KB Output is correct
7 Correct 1571 ms 32580 KB Output is correct
8 Correct 1728 ms 33768 KB Output is correct
9 Correct 1577 ms 32976 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 4343 ms 53188 KB Output is correct
2 Execution timed out 5000 ms 53188 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 362 ms 54920 KB Output is correct
6 Correct 340 ms 54728 KB Output is correct
7 Correct 386 ms 54920 KB Output is correct
8 Correct 356 ms 45512 KB Output is correct
9 Execution timed out 5000 ms 74844 KB Program timed out
10 Halted 0 ms 0 KB -