Submission #18762

#	Time	Username	Problem	Language	Result	Execution time	Memory
18762		pichulia	여왕벌 (KOI15_queen)	C++14	68 / 100	5000 ms	524288 KiB

Main

#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;
      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].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(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<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);
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 34 / 34
• Subtask 4: 0 / 32
• Subtask 5: 0 / 1