제출 #442542

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442542		zxcvbnm	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1092 ms	3908 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

5
3 2 2 -2 3 2 -3 -2 -2 -3

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

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

*/
int n;
map<vector<int>, int> used;
int mn = 30;
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) {
	n = s.size();
	vector<int> a = s;

	int sum = 0;
	for(int i = 0; i < n; i += 2) {
		for(int j = i+1; j < n; j++) {
			if (a[i] == -a[j]) {
				for(int k = j; k > i+1; k--) {
					swap(a[k], a[k-1]);
					sum++;
				}
				break;
			}
		}
		if (a[i] > a[i+1]) {
			swap(a[i], a[i+1]);
			sum++;
		}
//		for(int j : a) {
//			cout << j << " ";
//		}
//		cout << "\n";
	}
//	go(a, 0, temp1, temp2);

//	cout << mn << "\n";
	return sum;
}

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