oj.uz

Submission #632794

# Submission time Handle Problem Language Result Execution time Memory
632794 2022-08-20T20:08:26 Z flappybird None (JOI16_memory2) C++17
100 / 100
 1 ms 468 KB 
#include "Memory2_lib.h"
#include <bits/stdc++.h>
#include <cassert>
using namespace std;

#define MAX 200

int mp[MAX][MAX];
int chk[MAX];

int query(int x, int y) {
	if (x > y) swap(x, y);
	if (!~mp[x][y]) return mp[x][y] = Flip(x, y);
	return mp[x][y];
}

void Solve(int T, int N) {
	memset(mp, -1, sizeof(mp));
	vector<int> v;
	int i;
	while (1) {
		for (i = 0; i < N * 2; i++) if (!chk[i]) v.push_back(i);
		if (v.size() <= 2) {
			Answer(v[0], v[1], query(v[0], v[1]));
			return;
		}
		int M = v.size();
		vector<int> qarr, cnt(N);
		if (v.size() <= 4) {
			int j;
			for (i = 0; i < M; i++) for (j = i + 1; j < M; j++) cnt[query(v[i], v[j])]++;
			for (i = 0; i < N; i++) if (cnt[i] == 1) break;
			int k = i;
			for (i = 0; i < M; i++) for (j = i + 1; j < M; j++) {
				if (query(v[i], v[j]) == k) {
					Answer(v[i], v[j], k);
					chk[v[i]] = chk[v[j]] = 1;
				}
			}
			v.clear();
			continue;
		}
		for (i = 0; i < M; i++) qarr.push_back(query(v[i], v[(i + 1) % M]));
		int x, mx = 0;
		for (auto v : qarr) cnt[v]++, mx = max(mx, cnt[v]);
		for (i = 0; i < N; i++) if (cnt[i] == 4) break;
		if (i < N) {
			int k = i;
			int a, b;
			a = b = -1;
			for (i = 0; i < M; i++) if (qarr[i] != k && qarr[(i + 1) % M] == k) break;
			int num = M;
			for (; num >= 1; i = (i + 1) % M, num--) {
				if (qarr[i] == qarr[(i + 1) % M] && qarr[i] == k) {
					qarr[i] = -1;
					qarr[(i + 1) % M] = -1;
					assert(!~b);
					b = a, a = i;
				}
			}
			assert(~a);
			assert(~b);
			a++, a %= M;
			b++, b %= M;
			chk[v[a]] = chk[v[b]] = 1;
			Answer(v[a], v[b], k);
		}
		else {
			for (i = 0; i < M; i++) if (qarr[i] == qarr[(i + 1) % M] && qarr[i] == qarr[(i + 2) % M]) break;
			int k = qarr[i];
			int a, b, c, d;
			a = i, b = a + 1, c = b + 1, d = c + 1;
			a %= M;
			b %= M;
			c %= M;
			d %= M;
			if (query(v[a], v[d]) == k) {
				if (query(v[b], v[d]) == k) a = b, c = d;
				chk[v[a]] = chk[v[c]] = 1;
				Answer(v[a], v[c], k);
			}
			else {
				chk[v[b]] = chk[v[c]] = 1;
				Answer(v[b], v[c], k);
			}
		}
		v.clear();
	}
}

Compilation message

memory2.cpp: In function 'void Solve(int, int)':
memory2.cpp:44:7: warning: unused variable 'x' [-Wunused-variable]
   44 |   int x, mx = 0;
      |       ^

Subtask #1
10.0 / 10.0

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

Subtask #2
50.0 / 50.0

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

Subtask #3
40.0 / 40.0

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