Submission #1210330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210330		madamadam3	Arranging Shoes (IOI19_shoes)	C++20	0 / 100	0 ms	328 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

uint64_t hash_vec(const vector<int> &inp) {
	const uint64_t BASE = 998244353;
	uint64_t h = 0;
	for (int x : inp) {
		h = h * BASE + (uint32_t)x + 1;
	}

	return h;
}

int n;

struct State {
	vector<pair<int, int>> swaps;
	vector<int> arr;
	int moves;
	int p1, p2;
};

bool check_valid(State &state, vector<int> &initial) {
	vector<int> arrangement = initial;
	for (auto &el : state.swaps) {
		swap(arrangement[el.first], arrangement[el.second]);
	}

	bool valid = true;
	for (int i = 0; i < n; i++) {
		valid = valid && (abs(arrangement[2*i]) == abs(arrangement[2*i+1])) && (arrangement[2*i] < 0 && arrangement[2*i+1] > 0);
	}
	return valid;
}

bool check_valid(vector<int> &arrangement) {
	bool valid = true;
	for (int i = 0; i < n; i++) {
		valid = valid && (abs(arrangement[2*i]) == abs(arrangement[2*i+1])) && (arrangement[2*i] < 0 && arrangement[2*i+1] > 0);
	}
	return valid;
}


// left shoe if s[i] < 0
// right shoe if s[i] > 0
ll count_swaps(vector<int> s) {
	n = s.size() / 2;
	int minimum = 0;

	// queue<State> q;
	// State best;

	// q.push(State{{}, s, 0, -1, -1});
	// unordered_set<uint64_t> vis;
	// vis.insert(hash_vec(s));

	// while (!q.empty()) {
	// 	State cur = q.front();
	// 	q.pop();

	// 	// if (check_valid(cur, s)) {
	// 	if (check_valid(cur.arr)) {
	// 		minimum = cur.moves;
	// 		best = cur;
	// 		break;
	// 	}

	// 	for (int i = 1; i < 2*n; i++) {
	// 		for (int j = i-1; j < i+2 && j < 2*n; j++) {
	// 			if (i == j) continue;
	// 			if (((i == cur.p1) && (j == cur.p2)) || ((j == cur.p1) && (i == cur.p2))) continue;
	// 			// vector<pair<int, int>> swaps = cur.swaps;
	// 			// swaps.push_back({i, j});
	// 			// q.push(State{swaps, cur.moves + 1, i, j});

	// 			vector<int> cs = cur.arr;
	// 			swap(cs[i], cs[j]);
	// 			uint64_t h = hash_vec(cs);
	// 			if (vis.count(h)) continue;
	// 			vis.insert(h);

	// 			q.push(State{{}, cs, cur.moves + 1, i, j});
	// 		}
	// 	}
	// }
	
	// cout << "Fastest fix is " << best.moves << " moves\n";
	// for (auto &el : best.swaps) {
	// 	cout << "Swapped " << el.first << " and " << el.second << "\n";
	// }
	// return minimum;
	return n * (n - 1);
}

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