Submission #442528

#	Time	Username	Problem	Language	Result	Execution time	Memory
442528		zxcvbnm	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1097 ms	772076 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
/*
4
1 2 3 -4 4 -2 -1 -3

4
1 2 3 -4 -2 4 -1 -3

*/
int n;
map<vector<int>, int> used;
int mn = 40;
bool ok(vector<int> a) {
	for(int i = 0; i < n; i+=2) {
		if (a[i] == -a[i+1] && a[i] < 0) continue;
		return false;
	}
	return true;
}
void go(vector<int> a, int swaps, vector<vector<int>> path, map<int, int> add) {
	if (used.count(a) && used[a] <= swaps) return;
	if (swaps >= mn) return;
	used[a] = swaps;

	if (ok(a)) {
//		cout << swaps << "\n";
		if (swaps < mn) {
			mn = swaps;
//			cerr << mn << "\n";
//			for(auto i : path) {
//				for(int j : i) {
//					cout << j << " ";
//				}
//				cout << "\n";
//			}
//			cerr << "\n";
		}
//		for(auto i : add) {
//			cout << i.first << " " << i.second << "\n";
//		}
		return;
	}

	for(int i = 0; i < n; i++) {
		vector<int> b = a;
		if (i != 0) {
			add[b[i]]++;
			add[b[i-1]]++;
			swap(b[i-1], b[i]);
			path.push_back(b);
			go(b, swaps+1, path, add);
			path.pop_back();
			add[b[i]]--;
			add[b[i-1]]--;
			swap(b[i-1], b[i]);
		}
		if (i != n-1) {
			add[b[i]]++;
			add[b[i+1]]++;
			swap(b[i], b[i+1]);
			path.push_back(b);
			go(b, swaps+1, path, add);
			add[b[i]]--;
			add[b[i+1]]--;
			path.pop_back();
			swap(b[i], b[i+1]);
		}
	}
}
long long count_swaps(std::vector<int> s) {
	int cnt = 0;
	n = s.size();
	vector<int> a = s;

//	for(int i = 0; i < n; i += 2) {
//		if (a[i] != -a[i+1] || a[i] > 0) {
//			swap(a[i], a[i+1]);
//			cnt++;
//		}
//	}
	vector<vector<int>> path;
	map<int, int> add;
	go(a, 0, path, add);
	return mn;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:73:6: warning: unused variable 'cnt' [-Wunused-variable]
   73 |  int cnt = 0;
      |      ^~~

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