oj.uz

답안 #18773

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18773 2016-02-15T05:17:32 Z pichulia 여왕벌 (KOI15_queen) C++14
68 / 100
 5000 ms 524288 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;
					}
				}
			}
		}
		{
			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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 30116 KB Output is correct
2 Correct 0 ms 30116 KB Output is correct
3 Correct 5 ms 30116 KB Output is correct
4 Correct 9 ms 30116 KB Output is correct
5 Correct 53 ms 30116 KB Output is correct
6 Correct 37 ms 30116 KB Output is correct
7 Correct 38 ms 30116 KB Output is correct
8 Correct 64 ms 30116 KB Output is correct
9 Correct 97 ms 30116 KB Output is correct
10 Correct 221 ms 30116 KB Output is correct
11 Correct 264 ms 30116 KB Output is correct
12 Correct 263 ms 30116 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 30500 KB Output is correct
2 Correct 103 ms 30500 KB Output is correct
3 Correct 163 ms 30500 KB Output is correct
4 Correct 548 ms 30500 KB Output is correct
5 Correct 448 ms 30500 KB Output is correct
6 Correct 528 ms 30500 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 30308 KB Output is correct
2 Correct 38 ms 31628 KB Output is correct
3 Correct 317 ms 37508 KB Output is correct
4 Correct 1764 ms 62708 KB Output is correct
5 Correct 1540 ms 58196 KB Output is correct
6 Correct 1484 ms 48384 KB Output is correct
7 Correct 1836 ms 85092 KB Output is correct
8 Correct 2221 ms 106764 KB Output is correct
9 Correct 2512 ms 134096 KB Output is correct

Subtask #4
0.0 / 32.0

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

Subtask #5
0.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 30116 KB Output is correct
2 Correct 0 ms 30116 KB Output is correct
3 Correct 0 ms 30116 KB Output is correct
4 Correct 0 ms 30116 KB Output is correct
5 Correct 345 ms 54892 KB Output is correct
6 Correct 366 ms 54700 KB Output is correct
7 Correct 356 ms 54892 KB Output is correct
8 Correct 363 ms 45484 KB Output is correct
9 Memory limit exceeded 3872 ms 524288 KB Memory limit exceeded
10 Halted 0 ms 0 KB -