oj.uz

답안 #18772

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18772 2016-02-15T05:16:14 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];
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;
	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 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
			{
				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 = (int)(sqrt(m2))+1;
		for(j=0; j<m2; j+=em2)
		{
			for(l=0; l<=n;++l)
			{
				s[l].clear();
				v[l].clear();
			}
			int ee = min(m2, j+em2);
			for(i=j; i<ee;)
			{
				for(l=i+1; l<ee; ++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.0 / 10.0

# 결과 실행 시간 메모리 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 28 ms 30144 KB Output is correct
6 Correct 30 ms 30144 KB Output is correct
7 Correct 31 ms 30144 KB Output is correct
8 Correct 108 ms 30144 KB Output is correct
9 Correct 101 ms 30144 KB Output is correct
10 Correct 203 ms 30144 KB Output is correct
11 Correct 284 ms 30144 KB Output is correct
12 Correct 255 ms 30144 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 30528 KB Output is correct
2 Correct 111 ms 30528 KB Output is correct
3 Correct 171 ms 30528 KB Output is correct
4 Correct 539 ms 30528 KB Output is correct
5 Correct 522 ms 30528 KB Output is correct
6 Correct 573 ms 30528 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 30336 KB Output is correct
2 Correct 49 ms 30468 KB Output is correct
3 Correct 332 ms 30600 KB Output is correct
4 Correct 1653 ms 31920 KB Output is correct
5 Correct 1498 ms 31788 KB Output is correct
6 Correct 1542 ms 31788 KB Output is correct
7 Correct 1619 ms 32580 KB Output is correct
8 Correct 1815 ms 33768 KB Output is correct
9 Correct 1615 ms 32976 KB Output is correct

Subtask #4
0.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4412 ms 53188 KB Output is correct
2 Execution timed out 5000 ms 53188 KB Program timed out
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 1.0

# 결과 실행 시간 메모리 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 349 ms 54920 KB Output is correct
6 Correct 360 ms 54728 KB Output is correct
7 Correct 364 ms 54920 KB Output is correct
8 Correct 402 ms 45512 KB Output is correct
9 Execution timed out 5000 ms 74844 KB Program timed out
10 Halted 0 ms 0 KB -