Submission #1030474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030474		ender	Arranging Shoes (IOI19_shoes)	C++17	25 / 100	13 ms	3164 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;

}

long long bfs(vector<int> &src){

	//set<vector<int>> visited;
	map<vector<int>, bool> visited;
	map<vector<int>, long long> dist;

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

	while(!q.empty()){

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

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

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

			if(visited[move]) continue;

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


			if(check(move)) return dist[move];
		}
	}

}

vector<vector<int>> allperm(int n){

	vector<int> temp(n);

	for(int i = 0; i<n; ++i) temp[i] = i+1;

	vector<vector<int>> ans;

	do{



	}while(next_permutation(temp.begin(), temp.end()));

}

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


	if(s.size() == 2)
	return bfs(s);

	long long ans = 0;

	for(int i = 1; i < s.size()/2; ++i) ans += i;

	return ans;
}

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 'std::vector<std::vector<int> > allperm(int)':
shoes.cpp:82:1: warning: no return statement in function returning non-void [-Wreturn-type]
   82 | }
      | ^
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:92:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(int i = 1; i < s.size()/2; ++i) ans += i;
      |                 ~~^~~~~~~~~~~~
shoes.cpp: In function 'long long int bfs(std::vector<int>&)':
shoes.cpp:38:25: warning: control reaches end of non-void function [-Wreturn-type]
   38 |  map<vector<int>, bool> visited;
      |                         ^~~~~~~

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