Submission #152869

#	Time	Username	Problem	Language	Result	Execution time	Memory
152869		mieszko11b	Ancient Books (IOI17_books)	C++14	12 / 100	2064 ms	227184 KiB

books

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

using namespace std;

using ll = long long;

struct state {
	vector<int> V;
	int pos;
	int hand;
	
	state() {};
	state(vector<int> V, int pos, int hand) {
		this->V = V;
		this->pos = pos;
		this->hand = hand;
	}
};

bool operator<(const state &a, const state &b) {
	return make_tuple(a.V, a.pos, a.hand) < make_tuple(b.V, b.pos, b.hand);
}

vector<int> replace(vector<int> V, int i, int x) {
	V[i] = x;
	return V;
}

deque<state> Q;
map<state, int> dist;
map<state, bool> vis;

ll minimum_walk(std::vector<int> p, int s) {
	state ss(p, s, - 1);
	dist[ss] = 0;
	Q.push_front(ss);
	
	while(!Q.empty()) {
		state s = Q.front();
		vis[s] = 1;
		Q.pop_front();

		state s2 = s;
		swap(s2.V[s2.pos], s2.hand);
		if(!vis[s2]) {
			if(dist.count(s2) == 0)
				dist[s2] = 1e9;
			dist[s2] = min(dist[s2], dist[s]);
			Q.push_front(s2);
		}
		
		if(s.pos > 0) {
			s2 = s;
			s2.pos--;
			if(!vis[s2]) {
				if(dist.count(s2) == 0)
					dist[s2] = 1e9;
				dist[s2] = min(dist[s2], dist[s] + 1);
				Q.push_back(s2);
			}
		}
		
		if(s.pos + 1 < s.V.size()) {
			s2 = s;
			s2.pos++;
			if(!vis[s2]) {
				if(dist.count(s2) == 0)
					dist[s2] = 1e9;
				dist[s2] = min(dist[s2], dist[s] + 1);
				Q.push_back(s2);
			}
		}
	}
	
	sort(p.begin(), p.end());
	return dist[state(p, s, -1)];
}

Compilation message (stderr)

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:64:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(s.pos + 1 < s.V.size()) {
      ~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 0 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30