제출 #1278585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278585		trideser	Parking (CEOI22_parking)	C++20	0 / 100	2094 ms	135204 KiB

Main

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

int encryptstate(vector<pair<int, int>> v) {
	int ret = 0;
	for(pair<int, int> p : v) {
		int a, b;
		tie(a, b) = p;
		ret <<= 4;
		ret |= (a << 2) | b;
	}
	return ret;
}
vector<pair<int, int>> decryptstate(int state, int length) {
	vector<pair<int, int>> ret;
	for(int i = 4 * length - 4; i >= 0; i -= 4) {
		int current = state >> i;
		ret.push_back(make_pair((current & 0xc) >> 2, current & 0x3));
	}
	return ret;
}

void print(int state, unordered_map<int, tuple<int, int, int>>& states) {
	if(get<0>(states[state]) == -1) return;
	print(get<0>(states[state]), states);
	cout << get<1>(states[state]) + 1 << " " << get<2>(states[state]) + 1 << "\n";
}

int main() {
	int N, M;
	cin >> N >> M;
	unordered_map<int, tuple<int, int, int>> states;
	vector<pair<int, int>> start(M);
	for(int i = 0; i < M; i++) {
		int bot, top;
		cin >> bot >> top;
		start[i] = make_pair(bot, top);
	}
	int est = encryptstate(start);
	/*
	for(pair<int, int> p : start) cout << p.first << " " << p.second << ",";
	cout << "\n";
	for(pair<int, int> p : decryptstate(est, M)) cout << p.first << " " << p.second << ",";
	cout << "\n";*/
	states[est] = make_tuple(-1, -1, -1);
	if((est & 0x33333333) == (est & 0xcccccccc) >> 2) {
		cout << "0\n";
		return 0;
	}
	bool b = true;
	int loop = 0;
	while(b) {
		loop++;
		b = false;
		unordered_map<int, tuple<int, int, int>> newstates = states;
		for(auto it : states) {
			vector<pair<int, int>> stvec = decryptstate(it.first, M);
			for(int i = 0; i < M; i++) {
				for(int j = 0; j < M; j++) {
					if(i == j) continue;
					vector<pair<int, int>> newstvec = stvec;
					if(newstvec[i].first == 0)
						continue;
					if(newstvec[j].second != 0)
						continue;
					int num;
					if(stvec[i].second != 0) {
						num = stvec[i].second;
						newstvec[i].second = 0;
					}
					else {
						num = stvec[i].first;
						newstvec[i].first = 0;
					}
					if(stvec[j].first == 0)
						newstvec[j].first = num;
					else if(stvec[j].first == num)
						newstvec[j].second = num;
					else continue;

					int enc = encryptstate(newstvec);
					if(states.find(enc) == states.end() && newstates.find(enc) == newstates.end()) {
						//cout << i << " " << j << "\n";
						//for(pair<int, int> p : decryptstate(enc, M)) cout << p.first << " " << p.second << ",";
						//cout << "\n";
						b = true;
						newstates[enc] = make_tuple(it.first, i, j);
						//cout << "\t" << (enc & 0x33333333) << " " << ((enc & 0xcccccccc) >> 2) << "\n";
						if((enc & 0x33333333) == (enc & 0xcccccccc) >> 2) {
							states[enc] = make_tuple(it.first, i, j);
							cout << loop << "\n";
							print(enc, states);
							return 0;
						}
					}
				}
			}
		}
		states = newstates;
		//cout << states.size() << "\n";
	}
	cout << -1;
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 15
• Subtask 5: 0 / 25
• Subtask 6: 0 / 15