oj.uz

Submission #693324

# Submission time Handle Problem Language Result Execution time Memory
693324 2023-02-02T17:45:21 Z rainboy None (JOI16_memory2) C++17
100 / 100
 1 ms 292 KB 
#include "Memory2_lib.h"
#include <string.h>

const int N = 50;

int ei[N][2], eo[N];

void append(int a, int i) {
	ei[a][eo[a]++] = i;
}

int qu[N * 2];

void Solve(int t, int n) {
	t = t;
	memset(eo, 0, n * sizeof *eo);
	int cnt = 0;
	for (int i = 0; i < n * 2; i++)
		qu[cnt++] = i;
	while (cnt)
		if (cnt == 1) {
			int i = qu[--cnt];
			for (int a = 0; a < n; a++)
				if (eo[a] == 1) {
					append(a, i);
					break;
				}
		} else if (cnt == 2) {
			int i = qu[--cnt], j = qu[--cnt];
			bool done = false;
			for (int a = 0; a < n; a++)
				if (eo[a] == 0) {
					append(a, i), append(a, j);
					done = true;
					break;
				}
			if (done)
				continue;
			int a = -1, b = -1;
			for (int c = 0; c < n; c++)
				if (eo[c] == 1) {
					if (a == -1)
						a = c;
					else
						b = c;
				}
			if (Flip(ei[a][0], i) == a && Flip(ei[b][0], j) == b)
				append(a, i), append(b, j);
			else
				append(a, j), append(b, i);
		} else {
			int i = qu[--cnt], j = qu[--cnt], k = qu[--cnt];
			int a = Flip(i, j), b = Flip(j, k), c = Flip(k, i);
			if (a != b || b != c) {
				if (c == a)
					append(a, i), qu[cnt++] = j, qu[cnt++] = k;
				else if (a == b)
					append(b, j), qu[cnt++] = k, qu[cnt++] = i;
				else
					append(c, k), qu[cnt++] = i, qu[cnt++] = j;
			} else {
				while (cnt) {
					int l = qu[--cnt], d = Flip(l, i), e = Flip(l, j), f = Flip(l, k);
					if (d != e || e != f) {
						if (d == e)
							append(d, i), append(d, j), qu[cnt++] = k;
						else if (e == f)
							append(e, j), append(e, k), qu[cnt++] = i;
						else
							append(f, k), append(f, i), qu[cnt++] = j;
						qu[cnt++] = l;
						break;
					} else
						append(d, l);
				}
				if (cnt == 0) {
					int a = -1, b = -1;
					for (int c = 0; c < n; c++)
						if (eo[c] == 0)
							a = c;
						else if (eo[c] == 1)
							b = c;
					if (Flip(ei[b][0], i) == b)
						append(a, j), append(a, k), append(b, i);
					else if (Flip(ei[b][0], j) == b)
						append(a, k), append(a, i), append(b, j);
					else
						append(a, i), append(a, j), append(b, k);
				}
			}
		}
	for (int a = 0; a < n; a++)
		Answer(ei[a][0], ei[a][1], a);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 292 KB Output is correct
6 Correct 0 ms 224 KB Output is correct
7 Correct 0 ms 220 KB Output is correct
8 Correct 0 ms 228 KB Output is correct
9 Correct 1 ms 228 KB Output is correct
10 Correct 0 ms 220 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 224 KB Output is correct
10 Correct 1 ms 224 KB Output is correct