Submission #18776

#	Time	Username	Problem	Language	Result	Execution time	Memory
18776		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];
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);
	}
}

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