Submission #420444

#	Time	Username	Problem	Language	Result	Execution time	Memory
420444		QCFium	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	25 ms	3652 KiB

shoes

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

long long count_swaps(std::vector<int> a) {
	int n = a.size();
	assert(n <= 2000);
	int res = 0;
	while (a.size()) {
		int t = std::find(a.begin(), a.end(), -a[0]) - a.begin();
		res += t - 1;
		if (a[0] > 0) res++;
		a.erase(a.begin() + t);
		a.erase(a.begin());
	}
	return res;
}
long long count_swaps_gu(std::vector<int> a) {
	int n = a.size();
	
	std::map<std::vector<int>, int> dist;
	{
		auto b = a;
		std::sort(b.begin(), b.end());
		do {
			dist[b] = 1000000000;
		} while (std::next_permutation(b.begin(), b.end()));
	}
	
	std::queue<std::vector<int> > que;
	dist[a] = 0;
	que.push(a);
	while (que.size()) {
		auto i = que.front();
		que.pop();
		for (int j = 0; j + 1 < n; j++) {
			auto next = i;
			std::swap(next[j], next[j + 1]);
			if (dist[next] > dist[i] + 1) {
				dist[next] = dist[i] + 1;
				que.push(next);
			}
		}
	}
	int res = 1000000000;
	for (auto i : dist) {
		bool ok = true;
		for (int j = 0; j < n; j += 2) {
			if (i.first[j] > 0) ok = false;
			if (i.first[j + 1] < 0) ok = false;
			if (-i.first[j] != i.first[j + 1]) ok = false;
		}
		if (ok) res = std::min(res, i.second);
	}
	return res;
}

std::random_device rnd_dev;
std::mt19937 rnd(rnd_dev() ^ clock());
int rnd_int(int l, int r) { return std::uniform_int_distribution<>(l, r)(rnd); }


bool check() {
	int n = rnd_int(1, 5);
	std::vector<int> a;
	for (int i = 0; i < n; i++) a.push_back(rnd_int(1, n));
	for (int i = 0; i < n; i++) a.push_back(-a[i]);
	std::shuffle(a.begin(), a.end(), rnd);
	
	auto r0 = count_swaps(a);
	auto r1 = count_swaps_gu(a);
	if (r0 != r1) {
		std::cerr << "!!! FAILED !!!" << std::endl;
		for (auto i : a) std::cerr << i << " ";
		std::cerr << std::endl;
		std::cerr << "fast : " << r0 << std::endl;
		std::cerr << "gu   : " << r1 << std::endl;
		return false;
	}
	std::cerr << "ok : ";
	for (auto i : a) std::cerr << i << " ";
	std::cerr << std::endl;
	return true;
}

/*
int main() {
	for (int i = 0; i < 100000; i++) if (!check()) {
		std::cerr << "failed at " << i << std::endl;
		return 0;
	}
	return 0;
}*/

Compilation message (stderr)

shoes.cpp: In function 'int ri()':
shoes.cpp:5:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~

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