답안 #33232 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
33232	2017-10-23T04:14:40 Z	model_code	고대 책들 (IOI17_books)	C++11	12 / 100	2000 ms	1048576 KB

books

// Library solution for S=0 in O((N+2)!)
// Score: 20
// Use BFS over the entire state space

#include "books.h"
#include <vector>
#include <queue>
#include <map>
#include <iostream>

using namespace std;

struct state {
	int p; // Minas position
	int b; // Minas current book
	vector<int> s; // shelf
	bool operator < (const state &o) const {
		if(p != o.p) return p<o.p;
		if(b != o.b) return b<o.b;
		return s<o.s;
	}
	bool operator == (const state &o) const {
		return !(*this < o) && !(o < *this);
	}
	void print() const 	{
		cout << "state: p=" << p << " b=" << b << " s=[";
		for(int i=0; i<s.size(); i++) {
			if(i>0) cout << ",";
			cout << s[i];
		}
		cout << "] ";
	}
};

long long minimum_walk(vector<int> order, int s){
	int N = order.size();
	// BFS over the state space
	map<state, int> M; // Distance map for discovered states
	queue<state> Q; // BFS queue

	vector<int> initial(N);
	for(int i=0; i<N; i++) initial[i]=order[i];	
	state start = {0, -1, initial};

	vector<int> sorted(N);
	for(int i=0; i<N; i++) sorted[i]=i;
	state target = {0, -1, sorted};

	if(start==target) return 0;

	M[start] = 0;
	Q.push(start);

	while(!Q.empty()) {
		state s = Q.front(); Q.pop();
		vector<state> succ;
		// generate all possible successor states
		state ns = s;
		for(ns.p = s.p-1; ns.p <= s.p+1; ns.p++) { // next position +/- 1
			if(!(0<=ns.p && ns.p<N)) continue; // don't move out of the shelf

			swap(ns.b, ns.s[s.p]); 
			succ.push_back(ns); // swap only before the step
			swap(ns.b, ns.s[s.p]);

			swap(ns.b, ns.s[ns.p]); 
			succ.push_back(ns); // swap only after the step
			swap(ns.b, ns.s[ns.p]);

			swap(ns.b, ns.s[s.p]); swap(ns.b, ns.s[ns.p]);
			succ.push_back(ns); // swap before and after the step
			swap(ns.b, ns.s[ns.p]); swap(ns.b, ns.s[s.p]);
		}
		// explore all new successor states
		for(auto & ns : succ) {
			if(M.find(ns) == M.end()) {
				M[ns] = M[s] + 1;
				Q.push(ns);
			}
			if(ns == target) {
				return M[s] + 1;
			}
		}
	}
    return -1;
}

Compilation message

books.cpp: In member function 'void state::print() const':
books.cpp:27:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<s.size(); i++) {
                 ^

Subtask #1
12.0 / 12.0

#	결과	메모리	Grader output
1	Correct	2032 KB	Output is correct
2	Correct	2032 KB	Output is correct
3	Correct	2032 KB	Output is correct
4	Correct	2032 KB	Output is correct
5	Correct	2032 KB	Output is correct
6	Correct	2032 KB	Output is correct
7	Correct	2032 KB	Output is correct
8	Correct	2032 KB	Output is correct
9	Correct	2032 KB	Output is correct
10	Correct	2032 KB	Output is correct
11	Correct	2032 KB	Output is correct
12	Correct	2032 KB	Output is correct
13	Correct	2032 KB	Output is correct
14	Correct	2032 KB	Output is correct
15	Correct	2032 KB	Output is correct
16	Correct	2032 KB	Output is correct
17	Correct	2032 KB	Output is correct
18	Correct	2032 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2032 KB	Output is correct
2	Correct	0 ms	2032 KB	Output is correct
3	Correct	0 ms	2032 KB	Output is correct
4	Correct	0 ms	2032 KB	Output is correct
5	Correct	0 ms	2032 KB	Output is correct
6	Correct	0 ms	2032 KB	Output is correct
7	Correct	0 ms	2032 KB	Output is correct
8	Correct	0 ms	2032 KB	Output is correct
9	Correct	0 ms	2032 KB	Output is correct
10	Correct	0 ms	2032 KB	Output is correct
11	Correct	0 ms	2032 KB	Output is correct
12	Correct	0 ms	2032 KB	Output is correct
13	Correct	0 ms	2032 KB	Output is correct
14	Correct	0 ms	2032 KB	Output is correct
15	Correct	0 ms	2032 KB	Output is correct
16	Correct	0 ms	2032 KB	Output is correct
17	Correct	0 ms	2032 KB	Output is correct
18	Correct	0 ms	2032 KB	Output is correct
19	Execution timed out	2000 ms	1048576 KB	Execution timed out
20	Halted	0 ms	0 KB	-

Subtask #3
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2032 KB	Output is correct
2	Correct	0 ms	2032 KB	Output is correct
3	Correct	0 ms	2032 KB	Output is correct
4	Correct	0 ms	2032 KB	Output is correct
5	Correct	0 ms	2032 KB	Output is correct
6	Correct	0 ms	2032 KB	Output is correct
7	Correct	0 ms	2032 KB	Output is correct
8	Correct	0 ms	2032 KB	Output is correct
9	Correct	0 ms	2032 KB	Output is correct
10	Correct	0 ms	2032 KB	Output is correct
11	Correct	0 ms	2032 KB	Output is correct
12	Correct	0 ms	2032 KB	Output is correct
13	Correct	0 ms	2032 KB	Output is correct
14	Correct	0 ms	2032 KB	Output is correct
15	Correct	0 ms	2032 KB	Output is correct
16	Correct	0 ms	2032 KB	Output is correct
17	Correct	0 ms	2032 KB	Output is correct
18	Correct	0 ms	2032 KB	Output is correct
19	Execution timed out	2000 ms	1048576 KB	Execution timed out
20	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2000 ms	995000 KB	Execution timed out
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2032 KB	Output is correct
2	Correct	0 ms	2032 KB	Output is correct
3	Correct	0 ms	2032 KB	Output is correct
4	Correct	0 ms	2032 KB	Output is correct
5	Correct	0 ms	2032 KB	Output is correct
6	Correct	0 ms	2032 KB	Output is correct
7	Correct	0 ms	2032 KB	Output is correct
8	Correct	0 ms	2032 KB	Output is correct
9	Correct	0 ms	2032 KB	Output is correct
10	Correct	0 ms	2032 KB	Output is correct
11	Correct	0 ms	2032 KB	Output is correct
12	Correct	0 ms	2032 KB	Output is correct
13	Correct	0 ms	2032 KB	Output is correct
14	Correct	0 ms	2032 KB	Output is correct
15	Correct	0 ms	2032 KB	Output is correct
16	Correct	0 ms	2032 KB	Output is correct
17	Correct	0 ms	2032 KB	Output is correct
18	Correct	0 ms	2032 KB	Output is correct
19	Execution timed out	2000 ms	1048576 KB	Execution timed out
20	Halted	0 ms	0 KB	-

답안 #33232

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 0 / 10.0

Subtask #3 0 / 28.0

Subtask #4 0 / 20.0

Subtask #5 0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
0 / 10.0

Subtask #3
0 / 28.0

Subtask #4
0 / 20.0

Subtask #5
0 / 30.0