Submission #1278589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278589		trideser	Parking (CEOI22_parking)	C++20	10 / 100	2095 ms	135164 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 <<= 8;
		ret |= (a << 4) | b;
	}
	return ret;
}
vector<pair<int, int>> decryptstate(int state, int length) {
	vector<pair<int, int>> ret;
	for(int i = 8 * length - 8; i >= 0; i -= 8) {
		int current = state >> i;
		ret.push_back(make_pair((current & 0xf0) >> 4, current & 0xf));
	}
	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 & 0x0f0f0f0f) == (est & 0xf0f0f0f0) >> 4) {
		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(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 & 0x0f0f0f0f) == (enc & 0xf0f0f0f0) >> 4) {
							states[enc] = make_tuple(it.first, i, j);
							cout << loop << "\n";
							print(enc, states);
							return 0;
						}
					}
				}
			}
		}
		states = newstates;
		//cout << states.size() << "\n";
	}
	cout << "-1\n";
	return 0;
}

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