Submission #18761

# Submission time Handle Problem Language Result Execution time Memory
18761 2016-02-15T04:49:27 Z pichulia 여왕벌 (KOI15_queen) C++14
34 / 100
2523 ms 131560 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];
pair<int, pair<int, int>> b1[1000000];
pair<int, pair<int, int>> b2[1000000];
int m1, m2;


unordered_map<int, int> s[701];
unordered_map<int, 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 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].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 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;
	}
	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].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;
	{
		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[m2].first = i0;
				b2[m2].second.first = i1;
				b2[m2].second.second = i2;
				m2++;
			}
			else
			{
				b1[m1].first = i0;
				b1[m1].second.first = i1;
				b1[m1].second.second = i2;
				m1++;
			}
		}
		sort(b1, b1+m1);
		sort(b2,b2+m2);
		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(b2[k] != b2[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<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 time Memory Grader output
1 Correct 5 ms 53560 KB Output is correct
2 Correct 6 ms 53560 KB Output is correct
3 Correct 4 ms 53560 KB Output is correct
4 Correct 0 ms 53560 KB Output is correct
5 Correct 55 ms 53560 KB Output is correct
6 Correct 39 ms 53560 KB Output is correct
7 Correct 29 ms 53560 KB Output is correct
8 Correct 112 ms 53560 KB Output is correct
9 Correct 120 ms 53560 KB Output is correct
10 Correct 232 ms 53560 KB Output is correct
11 Correct 303 ms 53560 KB Output is correct
12 Correct 276 ms 53560 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 53560 KB Output is correct
2 Correct 118 ms 53560 KB Output is correct
3 Correct 180 ms 53560 KB Output is correct
4 Correct 644 ms 53560 KB Output is correct
5 Correct 498 ms 53560 KB Output is correct
6 Correct 529 ms 53560 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 53560 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2523 ms 131560 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 53560 KB Output is correct
2 Correct 0 ms 53560 KB Output is correct
3 Correct 0 ms 53560 KB Output is correct
4 Correct 0 ms 53560 KB Output is correct
5 Correct 259 ms 53560 KB Output is correct
6 Correct 357 ms 53560 KB Output is correct
7 Incorrect 195 ms 53560 KB Output isn't correct
8 Halted 0 ms 0 KB -