oj.uz

Submission #922743

# Submission time Handle Problem Language Result Execution time Memory
922743 2024-02-06T05:17:43 Z IBory None (JOI16_memory2) C++17
100 / 100
 1 ms 600 KB 
#include "Memory2_lib.h"
#include <bits/stdc++.h>
#include <random>
#define pii pair<int, int>
using namespace std;

const int MAX = 103;
int C[MAX];
vector<int> G[MAX];
map<pii, int> dp;

int _Flip(int a, int b) {
	if (a > b) swap(a, b);
	if (dp.find({a, b}) != dp.end()) return dp[{a, b}];
	int n = Flip(a, b);
	return dp[{a, b}] = n;
}

bool Process(int& a, int& b, int& c) {
	int QA = _Flip(a, b);
	int QB = _Flip(a, c);
	int QC = _Flip(b, c);
	if (QA == QB && QB == QC) return 0;

	if (QA == QB) C[a] = QA;
	else if (QA == QC) C[b] = QA, swap(a, b);
	else C[c] = QB, swap(a, c);
	return 1;
}

void Solve(int T, int N) {
	if (N == 1) {
		Answer(0, 1, 0);
		return;
	}

	N <<= 1;
	vector<int> P(N);
	iota(P.begin(), P.end(), 0);
	random_device rd;
	shuffle(P.begin(), P.end(), rd);

	memset(C, -1, sizeof(C));
	for (int i = 2; i < N; ++i) {
		int ok = Process(P[i - 2], P[i - 1], P[i]);
		if (!ok) {
			shuffle(P.begin() + i - 2, P.end(), rd);
			i--;
			continue;
		}
	}

	set<int> S;
	for (int i = 0; i < N / 2; ++i) S.insert(i);
	for (int i = 0; i < N; ++i) if (C[i] != -1 && S.find(C[i]) != S.end()) S.erase(C[i]);
	assert(S.size() == 1);
	int low = *S.begin();
	C[P[N - 1]] = C[P[N - 2]] = low;

	for (int i = 0; i < N / 2; ++i) {
		vector<int> ans;
		for (int j = 0; j < N; ++j) if (C[j] == i) ans.push_back(j);
		Answer(ans[0], ans[1], i);
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
50.0 / 50.0

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

Subtask #3
40.0 / 40.0

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