Submission #419031

#	Time	Username	Problem	Language	Result	Execution time	Memory
419031		jacquesamsel	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1132 ms	1048580 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
#define vint vector<int>
#define vvint vector<vint>

void print_vint(vint a) {
	for (auto x : a) cout << x << " ";
	cout << endl;
}
void print_vvint(vvint a) {
	cout << "-----" << endl;
	for (int i = 0; i < a.size(); i++) {
		print_vint(a[i]);
	}
	cout << "-----" << endl;
}

vint swap(vint& in, int pos) {
	vint a = vint(in.begin(), in.end());
	swap(a[pos], a[pos+1]);
	return a;
}

bool vint_done(vint a) {
	for (int i = 0; i < (a.size())/2; i++) {
		if (a[i*2] > 0 || a[i*2] != -a[i*2+1]) return false;
	}
	return true;
}

long long count_swaps(vector<int> s) {
	vvint book;
	vvint newBook;
	book.push_back(s);
	long long counter = 0;
	if (vint_done(s)) return 0;
	while (true) {
		for (auto b : book) {
			// print_vint(b);
			// if (vint_done(b)) {
			// 	return counter;
			// }
			// cout << "based off";
			// print_vint(b);
			for (int i = 0; i < s.size()-1; i++) {
				vint state = swap(b, i);
				// print_vint(state);
				if (vint_done(state)) {
					// cout << "CORRECT";
					// print_vint(state);
					return counter+1;
				}
				newBook.push_back(state);
			}
		}
		book = newBook;
		newBook = {};
		// cout << "ADD COUNTER" << endl;
		counter++;
	}
}

Compilation message (stderr)

shoes.cpp: In function 'void print_vvint(std::vector<std::vector<int> >)':
shoes.cpp:12:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for (int i = 0; i < a.size(); i++) {
      |                  ~~^~~~~~~~~~
shoes.cpp: In function 'bool vint_done(std::vector<int>)':
shoes.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for (int i = 0; i < (a.size())/2; i++) {
      |                  ~~^~~~~~~~~~~~~~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    for (int i = 0; i < s.size()-1; i++) {
      |                    ~~^~~~~~~~~~~~

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