Submission #41012

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
41012	2018-02-11T12:51:44 Z	alenam0161	Ancient Books (IOI17_books)	C++14	12 / 100	3 ms	820 KB

books

#include "books.h"
#include <vector>
#include <algorithm>
#include <stack>
#include <iostream>
using namespace std;
const int N = 1e6 + 7;
int group[N];
int mx[N];
bool used[N];
int par[N],lpar[N],rpar[N];
int fpar(int v) {
	return v == par[v] ? v : par[v] = fpar(par[v]);
}
void merge(int v, int u) {
	v = fpar(v);
	u = fpar(u);
	if (rand() & 1) {
		swap(u, v);
	}
	lpar[v] = min(lpar[v], lpar[u]);
	rpar[v] = max(rpar[v], rpar[u]);
	par[u] = v;
}
long long minimum_walk(std::vector<int> p, int s) {
	long long ans = 0;
	for (int i = 0; i < p.size(); ++i)
		par[i] = lpar[i] = rpar[i] = i;
	for (int i = 0; i < p.size(); ++i) {
		ans += abs(i - p[i]);
		merge(i, p[i]);
	}
	stack<int> st;
	for (int i = 0; i < p.size(); ++i) {
		int P = fpar(i);

		if (i == lpar[P]) {
			st.push(P);
		}
		else {
			while (fpar(i) != fpar(st.top())) {
				merge(i, st.top());
				st.pop();
			}
		}
		if (i == rpar[P])st.pop();
	}
	int L = 0, R = p.size() - 1;
	for (int i = p.size() - 1; i > 0; i--) { if (p[i] != i)break; R--; }
	for (int i = 0; i < p.size(); ++i) { if (p[i] != i)break;  L++; }
	int Main = fpar(s);
	int cl = lpar[Main];
	int cr = rpar[Main];
	while (cl > L || cr < R) {
		int howl = 0, ul = cl;
		while (ul > L) {
			ul--;
			howl++;
			int cur = fpar(ul);
			ul = lpar[cur];
			if (rpar[cur] > cr)break;
		}
		int howr = 0, ur = cr;
		while (ur < R) {
			ur++; howr++;
			int cur = fpar(ur);
			ur = rpar[cur];
			if (lpar[cur] < cl)break;
		}
		if (fpar(ul) == fpar(ur)) {
			int x = fpar(ul);
			cl = lpar[x];
			cr = rpar[x];
			ans += min(howl, howr) * 2;
		}
		else {
			cl = ul; cr = ur;
			ans += howl * 2 + howr * 2;
		}
	}

	return ans;
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); ++i)
                    ^
books.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); ++i) {
                    ^
books.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); ++i) {
                    ^
books.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); ++i) { if (p[i] != i)break;  L++; }
                    ^

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	352 KB	Output is correct
3	Correct	2 ms	404 KB	Output is correct
4	Correct	2 ms	460 KB	Output is correct
5	Correct	2 ms	460 KB	Output is correct
6	Correct	1 ms	532 KB	Output is correct
7	Correct	2 ms	532 KB	Output is correct
8	Correct	2 ms	532 KB	Output is correct
9	Correct	2 ms	604 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	2 ms	604 KB	Output is correct
12	Correct	2 ms	620 KB	Output is correct
13	Correct	1 ms	620 KB	Output is correct
14	Correct	2 ms	620 KB	Output is correct
15	Correct	1 ms	620 KB	Output is correct
16	Correct	2 ms	620 KB	Output is correct
17	Correct	2 ms	620 KB	Output is correct
18	Correct	2 ms	620 KB	Output is correct

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	352 KB	Output is correct
3	Correct	2 ms	404 KB	Output is correct
4	Correct	2 ms	460 KB	Output is correct
5	Correct	2 ms	460 KB	Output is correct
6	Correct	1 ms	532 KB	Output is correct
7	Correct	2 ms	532 KB	Output is correct
8	Correct	2 ms	532 KB	Output is correct
9	Correct	2 ms	604 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	2 ms	604 KB	Output is correct
12	Correct	2 ms	620 KB	Output is correct
13	Correct	1 ms	620 KB	Output is correct
14	Correct	2 ms	620 KB	Output is correct
15	Correct	1 ms	620 KB	Output is correct
16	Correct	2 ms	620 KB	Output is correct
17	Correct	2 ms	620 KB	Output is correct
18	Correct	2 ms	620 KB	Output is correct
19	Correct	2 ms	620 KB	Output is correct
20	Correct	2 ms	620 KB	Output is correct
21	Correct	2 ms	620 KB	Output is correct
22	Runtime error	2 ms	752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
23	Halted	0 ms	0 KB	-

Subtask #3
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	352 KB	Output is correct
3	Correct	2 ms	404 KB	Output is correct
4	Correct	2 ms	460 KB	Output is correct
5	Correct	2 ms	460 KB	Output is correct
6	Correct	1 ms	532 KB	Output is correct
7	Correct	2 ms	532 KB	Output is correct
8	Correct	2 ms	532 KB	Output is correct
9	Correct	2 ms	604 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	2 ms	604 KB	Output is correct
12	Correct	2 ms	620 KB	Output is correct
13	Correct	1 ms	620 KB	Output is correct
14	Correct	2 ms	620 KB	Output is correct
15	Correct	1 ms	620 KB	Output is correct
16	Correct	2 ms	620 KB	Output is correct
17	Correct	2 ms	620 KB	Output is correct
18	Correct	2 ms	620 KB	Output is correct
19	Correct	2 ms	620 KB	Output is correct
20	Correct	2 ms	620 KB	Output is correct
21	Correct	2 ms	620 KB	Output is correct
22	Runtime error	2 ms	752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
23	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	3 ms	820 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	352 KB	Output is correct
3	Correct	2 ms	404 KB	Output is correct
4	Correct	2 ms	460 KB	Output is correct
5	Correct	2 ms	460 KB	Output is correct
6	Correct	1 ms	532 KB	Output is correct
7	Correct	2 ms	532 KB	Output is correct
8	Correct	2 ms	532 KB	Output is correct
9	Correct	2 ms	604 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	2 ms	604 KB	Output is correct
12	Correct	2 ms	620 KB	Output is correct
13	Correct	1 ms	620 KB	Output is correct
14	Correct	2 ms	620 KB	Output is correct
15	Correct	1 ms	620 KB	Output is correct
16	Correct	2 ms	620 KB	Output is correct
17	Correct	2 ms	620 KB	Output is correct
18	Correct	2 ms	620 KB	Output is correct
19	Correct	2 ms	620 KB	Output is correct
20	Correct	2 ms	620 KB	Output is correct
21	Correct	2 ms	620 KB	Output is correct
22	Runtime error	2 ms	752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
23	Halted	0 ms	0 KB	-

Submission #41012

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