oj.uz

Submission #18727

# Submission time Handle Problem Language Result Execution time Memory
18727 2016-02-15T01:39:37 Z pichulia 여왕벌 (KOI15_queen) C++
68 / 100
 5000 ms 23644 KB 
#include<stdio.h>
#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];
int rr[701][701];
char x[999];
int p[709];
int q[709];
void process()
{
	int i0, i1, i2;
	int i, j, k, l;
	scanf("%d %d %d", &i0, &i1, &i2);
	// 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;
	}
	for (i = 1; i < n; i++)
	{
		int np, nq;
		np = p[i - 1];
		nq = q[i - 1];
		int si = 0;
		if (i0 + i1 < (n - i))si = 2;
		else if (i0 < (n - i)) si = 1;
		else si = 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;
	}
	r[0][p[0]]++;
	r[0][q[0]]++;
	for (i = 1; i < n; i++)
	{
		//	printf("%d %d\n", p[i], q[i]);
		r[i][p[i-1]]--;
		r[i][q[i-1]]--;
		r[i][p[i]]++;
		r[i][q[i]]++;
	}
}
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();
	{
		while (m--)
		{
			process();
		}
		for (j = 0; j < n; j++)
		{
			k = 0;
			for (i = 0; i < n; i++)
			{
				k += r[i][j];
				rr[i][j] = k;
			}
		}
		for (i = 0; i < n; i++)
		{
			k = 1;
			for (j = 0; j < n; j++)
			{
				k += rr[i][j];
				printf("%d ", k);
			}
			printf("\n");
		}
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 23644 KB Output is correct
2 Correct 0 ms 23644 KB Output is correct
3 Correct 0 ms 23644 KB Output is correct
4 Correct 5 ms 23644 KB Output is correct
5 Correct 42 ms 23644 KB Output is correct
6 Correct 35 ms 23644 KB Output is correct
7 Correct 23 ms 23644 KB Output is correct
8 Correct 120 ms 23644 KB Output is correct
9 Correct 102 ms 23644 KB Output is correct
10 Correct 198 ms 23644 KB Output is correct
11 Correct 258 ms 23644 KB Output is correct
12 Correct 249 ms 23644 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 23644 KB Output is correct
2 Correct 95 ms 23644 KB Output is correct
3 Correct 82 ms 23644 KB Output is correct
4 Correct 388 ms 23644 KB Output is correct
5 Correct 364 ms 23644 KB Output is correct
6 Correct 367 ms 23644 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23644 KB Output is correct
2 Correct 19 ms 23644 KB Output is correct
3 Correct 250 ms 23644 KB Output is correct
4 Correct 431 ms 23644 KB Output is correct
5 Correct 539 ms 23644 KB Output is correct
6 Correct 537 ms 23644 KB Output is correct
7 Correct 533 ms 23644 KB Output is correct
8 Correct 505 ms 23644 KB Output is correct
9 Correct 349 ms 23644 KB Output is correct

Subtask #4
0.0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 23640 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 23644 KB Output is correct
2 Correct 0 ms 23644 KB Output is correct
3 Correct 0 ms 23644 KB Output is correct
4 Correct 0 ms 23644 KB Output is correct
5 Correct 166 ms 23644 KB Output is correct
6 Correct 314 ms 23644 KB Output is correct
7 Correct 306 ms 23644 KB Output is correct
8 Correct 307 ms 23644 KB Output is correct
9 Execution timed out 5000 ms 23644 KB Program timed out
10 Halted 0 ms 0 KB -