제출 #1016881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1016881		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1079 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;

}

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];
		}
	}

}

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

	return bfs(s);

	//long long ans = 0;

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

	//return ans;
}

컴파일 시 표준 에러 (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 '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: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15