제출 #1192656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192656		JooDdae	Memory 2 (JOI16_memory2)	C++20	10 / 100	0 ms	328 KiB

memory2

#include "Memory2_lib.h"
#include<bits/stdc++.h>
using namespace std;

void Solve(int T, int N) {
	int M = N+N;
	vector<vector<int>> q(M, vector<int>(M, -1));

	if(N <= 12) {
		for(int i=0;i<M;i++) for(int j=i+1;j<M;j++) q[i][j] = q[j][i] = Flip(i, j);

		vector<int> chk(N, 0);
		for(int r=0;r<N;r++) {
			vector<int> v;
			for(int i=0;i<M;i++) {
				set<int> S;
				for(int j=0;j<M;j++) if(!chk[q[i][j]]) S.insert(q[i][j]);
				if(S.size() == 1) v.push_back(i);
			}

			int u = q[v[0]][v[1]];
			Answer(v[0], v[1], u), chk[u] = 1;
		}
		return;
	}

	random_device rd;
	mt19937 g(rd());
	vector<int> id(M); iota(id.begin(), id.end(), 0);
	shuffle(id.begin(), id.end(), g);

	array<int, 2> v = {id[0], id[1]};
	q[id[0]][id[1]] = q[id[1]][id[0]] = Flip(id[0], id[1]);
	for(int j=2;j<M;j++) {
		int i = id[j];
		auto [x, y] = v;
		q[x][i] = q[i][x] = Flip(x, i);
		q[y][i] = q[i][y] = Flip(y, i);

		if(q[x][y] == q[x][i] && q[x][i] == q[y][i]) {
			while(1) {
				int u = rand() % M;
				if(u == x || u == y || u == i) continue;

				int X = q[x][u] == -1 ? q[u][x] = q[x][u] = Flip(x, u) : q[x][u];
				int Y = q[y][u] == -1 ? q[u][y] = q[y][u] = Flip(y, u) : q[y][u];

				if(X != Y) break;

				int I = q[u][i] == -1 ? q[u][i] = q[i][u] = Flip(i, u) : q[i][u];
				if(X != I) {
					v = {x, i};
					break;
				}
				if(Y != I) {
					v = {y, i};
					break;
				}
			}
		} else {
			if(q[x][i] == q[x][y]) v = {y, i};
			else if(q[y][i] == q[x][y]) v = {x, i};
		}
	}
	Answer(v[0], v[1], q[v[0]][v[1]]);

	vector<int> c(N, -1);
	for(int i=0;i<M;i++) if(i != v[0] && i != v[1]) {
		int u = Flip(i, v[0]);

		if(c[u] != -1) Answer(c[u], i, u);
		else c[u] = i;
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 50
• Subtask 3: 0 / 40