Submission #1016857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016857		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1101 ms	1048576 KiB

shoes

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

using namespace std;

bool check(vector<int> &x){

	for(int i = 1; i < x.size(); i += 2){

		if((x[i-1] < x[i]) && (x[i-1]*-1 == x[i])) continue;
		else return false;

	}

	return true;

}

vector<vector<int>> moves(vector<int> &a){

	vector<vector<int>> ans;

	for(int i = 1; i < a.size(); ++i){

		vector<int> temp(a.begin(), a.end());
		swap(temp[i-1], temp[i]);
		ans.push_back(temp);

	}

	return ans;

}

int bfs(vector<int> &src){

	set<vector<int>> visited;
	map<vector<int>, int> dist;

	queue<vector<int>> q;
	visited.insert(src);
	dist[src] = 0;
	q.push(src);

	while(!q.empty()){

		vector<int> act = q.front(); q.pop();

		if(check(act)) return dist[act];

		for(const auto &move : moves(act)){

			if(visited.count(move)) continue;

			dist[move] = dist[act] + 1;
			visited.insert(move);
			q.push(move);

		}
	}

}

long long count_swaps(std::vector<int> s) {

	return bfs(s);
}

Compilation message (stderr)

shoes.cpp: In function 'bool check(std::vector<int>&)':
shoes.cpp:8:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |  for(int i = 1; i < x.size(); i += 2){
      |                 ~~^~~~~~~~~~
shoes.cpp: In function 'std::vector<std::vector<int> > moves(std::vector<int>&)':
shoes.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for(int i = 1; i < a.size(); ++i){
      |                 ~~^~~~~~~~~~
shoes.cpp: In function 'int bfs(std::vector<int>&)':
shoes.cpp:37:19: warning: control reaches end of non-void function [-Wreturn-type]
   37 |  set<vector<int>> visited;
      |                   ^~~~~~~

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