Submission #1030687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030687		fv3	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1054 ms	1048576 KiB

shoes

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

using namespace std;
typedef long long ll;

bool isValid(vector<int> v)
{
	for (int i = 0; i < v.size(); i += 2)
	{
		if (v[i] > v[i+1] || v[i] != -v[i+1])
			return false;
	}
	return true;
}

ll count_swaps(vector<int> s) 
{
	const int N = s.size() / 2;

	map<vector<int>, int> visited;
	visited[s] = 0;
	queue<vector<int>> q;
	q.push(s);

	while (!q.empty())
	{
		vector<int> v = q.front();
		int d = visited[v];
		if (isValid(v))
		{
			return d;
		}
		q.pop();

		for (int i = 0; i < 2 * N - 1; i++)
		{
			swap(v[i], v[i+1]);

			if (visited.count(v) == 0)
			{
				visited[v] = d + 1;
				q.push(v);
			}

			swap(v[i], v[i+1]);
		}
	}

	return 0;
}

Compilation message (stderr)

shoes.cpp: In function 'bool isValid(std::vector<int>)':
shoes.cpp:9:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |  for (int i = 0; i < v.size(); i += 2)
      |                  ~~^~~~~~~~~~

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