Submission #33236

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
33236	2017-10-23T04:15:35 Z	model_code	Ancient Books (IOI17_books)	C++11	100 / 100	273 ms	21560 KB

books

// Library solution for all S in O(N)
// Score: 100
#include "books.h"
#include <cstdlib>
#include <vector>
#include <map>
#include <iostream>
#include <cassert>

using namespace std;
using VI = vector<int>;

// Compute extend(l,r), initially assuming that the only
// cycles not checked yet are C[l] and C[r].
void extend(int &l, int &r, VI &C, VI &L, VI &R) {
	// [ll, rr] is always the current extension,
	// while only [l,r] was already checked for
	// further overlapping cycles.
	int ll = l, rr = r;
	ll = min(ll,min(L[C[l]], L[C[r]]));
	rr = max(rr,max(R[C[l]], R[C[r]]));

	while(ll<l || r<rr) {
		if(ll<l) {
			l--;
			ll = min(ll,L[C[l]]);
			rr = max(rr,R[C[l]]);
		} else {
			r++;
			ll = min(ll,L[C[r]]);
			rr = max(rr,R[C[r]]);
		}
	}
}

// Compute the remaining cost of non-essentially connecting all the cycles
// if we already connected from S to [l,r] but need to go until we covered
// all of [target_l, target_r].
int connect(int l, int r, int target_l, int target_r, VI &C, VI &L, VI &R) {
	int cost = 0;

	// Repeat as long as [l,r] != [target_l, target_r]
	do {
		extend(l,r,C,L,R);
		// Compute whether there is a next S-including cycle C_l to the left of l 
		// and its reaching cost c_l.
		bool next_l = false; // Does C_l exist?
		int cost_l = 0;
		int l_l=l, r_l=r; // Temporary interval [l_l, r_l].
		while(true) {
			if(l_l<=target_l) break;
			l_l--;
			cost_l += 2;
			extend(l_l,r_l,C,L,R);
			if(r_l>r) { // Detect extension on the other side.
				next_l = true;
				break;
			}
		}
		// Compute whether there is a next S-including cycle C_r to the right of r
		// and its reaching cost c_r.
		bool next_r = false; // Does C_r exist?
		int cost_r = 0;
		int l_r=l, r_r=r; // Temporary interval [l_r, r_r].
		while(true) {
			if(r_r>=target_r) break;
			r_r++;
			cost_r += 2;
			extend(l_r,r_r,C,L,R);
			if(l_r<l) { // Detect extension on the other side.
				next_r = true;
				break;
			}
		}
		// Either there was an S-including cycle on both sides or on none.
		assert(!(next_l ^ next_r)); 
		if(next_l && next_r) { // We can extend on both sides.
			cost += min(cost_l, cost_r); // Take the cheaper of both options.
		} else {
			// If there are no more S-including cycles, then we have to 
			// walk the necessary non-essential steps on both sides.
			cost += cost_l + cost_r;
		}
		// New interval [l,r] = extend(C_l \cup C_r).
		l = min(l_l, l_r);
		r = max(r_l, r_r);
	} while(target_l<l || r<target_r); // As long as Mina needs to explore more.
	return cost;
}

long long minimum_walk(vector<int> order, int S) {
	int N = order.size();
	long long int dP = 0;
	
	// For every slot i, determine its cycle C[i].
	// For every cycle c, determine its interval [L[c], R[c]].
	vector<int> C(N, -1), L(N), R(N);
	int l = S, r = S; // Compute the range that Mina needs to visit.
	int c = 0; // Number of cycles of Pi.
	for(int i=0; i<N; i++) {
		dP += abs(i-order[i]); // Compute d(pi).
		if(C[i] == -1) { // New cycle detected.
			L[c] = i; R[c] = i; // Initialize its leftmost and rightmost slot
			int j = i;
			do { // Loop over the cycle.
				C[j] = c;
				R[c] = max(R[c], j);
				j = order[j];
			} while (i != j);
			if(i != order[i]) {
				// If the cycle is non-trivial, it needs to be part of the
				// range that Mina has to visit.
				l = min(l,L[c]);
				r = max(r,R[c]);
			}
			c++; // Finished processing the cycle containing slot i.
		}
	}
	// Add up the number essential and non-essential steps needed.
	return dP+connect(S, S, l, r, C, L, R);
}

Subtask #1
12.0 / 12.0

#	Verdict	Memory	Grader output
1	Correct	2020 KB	Output is correct
2	Correct	2020 KB	Output is correct
3	Correct	2020 KB	Output is correct
4	Correct	2020 KB	Output is correct
5	Correct	2020 KB	Output is correct
6	Correct	2020 KB	Output is correct
7	Correct	2020 KB	Output is correct
8	Correct	2020 KB	Output is correct
9	Correct	2020 KB	Output is correct
10	Correct	2020 KB	Output is correct
11	Correct	2020 KB	Output is correct
12	Correct	2020 KB	Output is correct
13	Correct	2020 KB	Output is correct
14	Correct	2020 KB	Output is correct
15	Correct	2020 KB	Output is correct
16	Correct	2020 KB	Output is correct
17	Correct	2020 KB	Output is correct
18	Correct	2020 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	2020 KB	Output is correct
2	Correct	2020 KB	Output is correct
3	Correct	2020 KB	Output is correct
4	Correct	2020 KB	Output is correct
5	Correct	2020 KB	Output is correct
6	Correct	2020 KB	Output is correct
7	Correct	2020 KB	Output is correct
8	Correct	2020 KB	Output is correct
9	Correct	2020 KB	Output is correct
10	Correct	2020 KB	Output is correct
11	Correct	2020 KB	Output is correct
12	Correct	2020 KB	Output is correct
13	Correct	2020 KB	Output is correct
14	Correct	2020 KB	Output is correct
15	Correct	2020 KB	Output is correct
16	Correct	2020 KB	Output is correct
17	Correct	2020 KB	Output is correct
18	Correct	2020 KB	Output is correct
19	Correct	2020 KB	Output is correct
20	Correct	2020 KB	Output is correct
21	Correct	2020 KB	Output is correct
22	Correct	2020 KB	Output is correct
23	Correct	2020 KB	Output is correct
24	Correct	2020 KB	Output is correct
25	Correct	2020 KB	Output is correct
26	Correct	2020 KB	Output is correct
27	Correct	2020 KB	Output is correct
28	Correct	2020 KB	Output is correct
29	Correct	2020 KB	Output is correct

Subtask #3
28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2020 KB	Output is correct
2	Correct	0 ms	2020 KB	Output is correct
3	Correct	0 ms	2020 KB	Output is correct
4	Correct	0 ms	2020 KB	Output is correct
5	Correct	0 ms	2020 KB	Output is correct
6	Correct	0 ms	2020 KB	Output is correct
7	Correct	0 ms	2020 KB	Output is correct
8	Correct	0 ms	2020 KB	Output is correct
9	Correct	0 ms	2020 KB	Output is correct
10	Correct	0 ms	2020 KB	Output is correct
11	Correct	0 ms	2020 KB	Output is correct
12	Correct	0 ms	2020 KB	Output is correct
13	Correct	0 ms	2020 KB	Output is correct
14	Correct	0 ms	2020 KB	Output is correct
15	Correct	0 ms	2020 KB	Output is correct
16	Correct	0 ms	2020 KB	Output is correct
17	Correct	0 ms	2020 KB	Output is correct
18	Correct	0 ms	2020 KB	Output is correct
19	Correct	0 ms	2020 KB	Output is correct
20	Correct	0 ms	2020 KB	Output is correct
21	Correct	0 ms	2020 KB	Output is correct
22	Correct	0 ms	2020 KB	Output is correct
23	Correct	0 ms	2020 KB	Output is correct
24	Correct	0 ms	2020 KB	Output is correct
25	Correct	0 ms	2020 KB	Output is correct
26	Correct	0 ms	2020 KB	Output is correct
27	Correct	0 ms	2020 KB	Output is correct
28	Correct	0 ms	2020 KB	Output is correct
29	Correct	0 ms	2020 KB	Output is correct
30	Correct	209 ms	21560 KB	Output is correct
31	Correct	273 ms	21560 KB	Output is correct
32	Correct	153 ms	21560 KB	Output is correct
33	Correct	173 ms	21560 KB	Output is correct
34	Correct	173 ms	21560 KB	Output is correct
35	Correct	153 ms	21560 KB	Output is correct
36	Correct	193 ms	21560 KB	Output is correct
37	Correct	159 ms	21560 KB	Output is correct
38	Correct	199 ms	21560 KB	Output is correct
39	Correct	176 ms	21560 KB	Output is correct
40	Correct	166 ms	21560 KB	Output is correct
41	Correct	213 ms	21560 KB	Output is correct
42	Correct	213 ms	21560 KB	Output is correct
43	Correct	169 ms	21560 KB	Output is correct

Subtask #4
20.0 / 20.0

#	Verdict	Memory	Grader output
1	Correct	2020 KB	Output is correct
2	Correct	2020 KB	Output is correct
3	Correct	2020 KB	Output is correct
4	Correct	2020 KB	Output is correct
5	Correct	2020 KB	Output is correct
6	Correct	2020 KB	Output is correct
7	Correct	2020 KB	Output is correct
8	Correct	2020 KB	Output is correct
9	Correct	2020 KB	Output is correct
10	Correct	2020 KB	Output is correct
11	Correct	2020 KB	Output is correct
12	Correct	2020 KB	Output is correct
13	Correct	2020 KB	Output is correct
14	Correct	2020 KB	Output is correct
15	Correct	2020 KB	Output is correct
16	Correct	2020 KB	Output is correct
17	Correct	2020 KB	Output is correct
18	Correct	2020 KB	Output is correct
19	Correct	2020 KB	Output is correct
20	Correct	2020 KB	Output is correct

Subtask #5
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2020 KB	Output is correct
2	Correct	0 ms	2020 KB	Output is correct
3	Correct	0 ms	2020 KB	Output is correct
4	Correct	0 ms	2020 KB	Output is correct
5	Correct	0 ms	2020 KB	Output is correct
6	Correct	0 ms	2020 KB	Output is correct
7	Correct	0 ms	2020 KB	Output is correct
8	Correct	0 ms	2020 KB	Output is correct
9	Correct	0 ms	2020 KB	Output is correct
10	Correct	0 ms	2020 KB	Output is correct
11	Correct	0 ms	2020 KB	Output is correct
12	Correct	0 ms	2020 KB	Output is correct
13	Correct	0 ms	2020 KB	Output is correct
14	Correct	0 ms	2020 KB	Output is correct
15	Correct	0 ms	2020 KB	Output is correct
16	Correct	0 ms	2020 KB	Output is correct
17	Correct	0 ms	2020 KB	Output is correct
18	Correct	0 ms	2020 KB	Output is correct
19	Correct	0 ms	2020 KB	Output is correct
20	Correct	0 ms	2020 KB	Output is correct
21	Correct	0 ms	2020 KB	Output is correct
22	Correct	0 ms	2020 KB	Output is correct
23	Correct	0 ms	2020 KB	Output is correct
24	Correct	0 ms	2020 KB	Output is correct
25	Correct	0 ms	2020 KB	Output is correct
26	Correct	0 ms	2020 KB	Output is correct
27	Correct	0 ms	2020 KB	Output is correct
28	Correct	0 ms	2020 KB	Output is correct
29	Correct	0 ms	2020 KB	Output is correct
30	Correct	209 ms	21560 KB	Output is correct
31	Correct	273 ms	21560 KB	Output is correct
32	Correct	153 ms	21560 KB	Output is correct
33	Correct	173 ms	21560 KB	Output is correct
34	Correct	173 ms	21560 KB	Output is correct
35	Correct	153 ms	21560 KB	Output is correct
36	Correct	193 ms	21560 KB	Output is correct
37	Correct	159 ms	21560 KB	Output is correct
38	Correct	199 ms	21560 KB	Output is correct
39	Correct	176 ms	21560 KB	Output is correct
40	Correct	166 ms	21560 KB	Output is correct
41	Correct	213 ms	21560 KB	Output is correct
42	Correct	213 ms	21560 KB	Output is correct
43	Correct	169 ms	21560 KB	Output is correct
44	Correct	0 ms	2020 KB	Output is correct
45	Correct	0 ms	2020 KB	Output is correct
46	Correct	0 ms	2020 KB	Output is correct
47	Correct	0 ms	2020 KB	Output is correct
48	Correct	0 ms	2020 KB	Output is correct
49	Correct	0 ms	2020 KB	Output is correct
50	Correct	0 ms	2020 KB	Output is correct
51	Correct	0 ms	2020 KB	Output is correct
52	Correct	0 ms	2020 KB	Output is correct
53	Correct	0 ms	2020 KB	Output is correct
54	Correct	0 ms	2020 KB	Output is correct
55	Correct	0 ms	2020 KB	Output is correct
56	Correct	0 ms	2020 KB	Output is correct
57	Correct	0 ms	2020 KB	Output is correct
58	Correct	0 ms	2020 KB	Output is correct
59	Correct	0 ms	2020 KB	Output is correct
60	Correct	0 ms	2020 KB	Output is correct
61	Correct	0 ms	2020 KB	Output is correct
62	Correct	0 ms	2020 KB	Output is correct
63	Correct	0 ms	2020 KB	Output is correct
64	Correct	146 ms	21560 KB	Output is correct
65	Correct	149 ms	21560 KB	Output is correct
66	Correct	153 ms	21560 KB	Output is correct
67	Correct	159 ms	21560 KB	Output is correct
68	Correct	6 ms	3980 KB	Output is correct
69	Correct	19 ms	3980 KB	Output is correct
70	Correct	13 ms	3980 KB	Output is correct
71	Correct	16 ms	3980 KB	Output is correct
72	Correct	13 ms	3980 KB	Output is correct
73	Correct	26 ms	3980 KB	Output is correct
74	Correct	156 ms	21560 KB	Output is correct
75	Correct	183 ms	21560 KB	Output is correct
76	Correct	173 ms	21560 KB	Output is correct
77	Correct	153 ms	21560 KB	Output is correct
78	Correct	179 ms	21560 KB	Output is correct
79	Correct	173 ms	21560 KB	Output is correct
80	Correct	149 ms	21560 KB	Output is correct
81	Correct	159 ms	21560 KB	Output is correct
82	Correct	159 ms	21560 KB	Output is correct
83	Correct	173 ms	21560 KB	Output is correct
84	Correct	179 ms	21560 KB	Output is correct
85	Correct	149 ms	21560 KB	Output is correct
86	Correct	196 ms	21560 KB	Output is correct
87	Correct	176 ms	21560 KB	Output is correct
88	Correct	163 ms	21560 KB	Output is correct
89	Correct	169 ms	21560 KB	Output is correct
90	Correct	176 ms	21560 KB	Output is correct
91	Correct	183 ms	21560 KB	Output is correct
92	Correct	153 ms	21560 KB	Output is correct

Submission #33236

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 28.0 / 28.0

Subtask #4 20.0 / 20.0

Subtask #5 30.0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
10.0 / 10.0

Subtask #3
28.0 / 28.0

Subtask #4
20.0 / 20.0

Subtask #5
30.0 / 30.0