제출 #922743

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
922743		IBory	Memory 2 (JOI16_memory2)	C++17	100 / 100	1 ms	600 KiB

memory2

#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 / 10
• Subtask 2: 50 / 50
• Subtask 3: 40 / 40