oj.uz

Submission #18735

# Submission time Handle Problem Language Result Execution time Memory
18735 2016-02-15T02:39:34 Z pichulia 여왕벌 (KOI15_queen) C++14
34 / 100
 4807 ms 36664 KB 
#include<stdio.h>
#include<unordered_map>
#include<unordered_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 r[701][701];
char x[999];
int p[709];
int q[709];
pair<int, pair<int, int>> b[1000000];

unordered_map<int, int> s[701];
unordered_map<int, unordered_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 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;
		si=2;
	}
	else if (i0 < n)
	{
		p[0] = 0; q[0] = n - i2;
		si=1;
	}
	else
	{
		p[0] = i0 - n + 1; q[0] = n - i2;
		si=0;
	}
	hi = hashing(si, p[0], q[0]);
	if(s[0].count(hi)){
		s[0][hi]++;
	}
	else
		s[0][hi] = 1;
	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 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;
	}
}
int main()
{
	scanf("%d %d", &n, &m);
	int i, j, k;
	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();
	{
		for(i=0; i<m; i++)
		{
			scanf("%d %d %d", &b[i].first, &b[i].second.first, &b[i].second.second);
		}
		sort(b,b+m);
		for(i=0;i<m;)
		{
			for(j=0; j<=n;j++)
			{
				s[j].clear();
				v[j].clear();
			}
			for(j=i+1;j<m;j++)
				if(b[i].first != b[j].first)
					break;
			for(k=i; k<j; k++)
			{
				process(b[k].first, b[k].second.first, b[k].second.second);
			}
			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 (i = 0; i < n; i++)
		{
			k = 1;
			for (j = 0; j < n; j++)
			{
				k += r[i][j];
				printf("%d ", k);
			}
			printf("\n");
		}
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 34156 KB Output is correct
2 Correct 0 ms 34156 KB Output is correct
3 Correct 11 ms 34156 KB Output is correct
4 Correct 0 ms 34156 KB Output is correct
5 Correct 47 ms 34156 KB Output is correct
6 Correct 37 ms 34156 KB Output is correct
7 Correct 27 ms 34156 KB Output is correct
8 Correct 99 ms 34156 KB Output is correct
9 Correct 98 ms 34156 KB Output is correct
10 Correct 230 ms 34288 KB Output is correct
11 Correct 237 ms 34288 KB Output is correct
12 Correct 237 ms 34288 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 34156 KB Output is correct
2 Correct 104 ms 34156 KB Output is correct
3 Correct 188 ms 34156 KB Output is correct
4 Correct 672 ms 34288 KB Output is correct
5 Correct 586 ms 34288 KB Output is correct
6 Correct 658 ms 34288 KB Output is correct

Subtask #3
0.0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 34156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 4807 ms 36664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 34156 KB Output is correct
2 Correct 0 ms 34156 KB Output is correct
3 Correct 5 ms 34156 KB Output is correct
4 Correct 0 ms 34156 KB Output is correct
5 Incorrect 486 ms 34156 KB Output isn't correct
6 Halted 0 ms 0 KB -