oj.uz

Submission #41011

# Submission time Handle Problem Language Result Execution time Memory
41011 2018-02-11T12:48:26 Z alenam0161 Ancient Books (IOI17_books) C++14
12 / 100
 3 ms 828 KB 
#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(fpar(i), fpar(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(fpar(i), fpar(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 1 ms 356 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 2 ms 532 KB Output is correct
6 Correct 2 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 536 KB Output is correct
10 Correct 2 ms 548 KB Output is correct
11 Correct 2 ms 548 KB Output is correct
12 Correct 2 ms 552 KB Output is correct
13 Correct 2 ms 552 KB Output is correct
14 Correct 2 ms 568 KB Output is correct
15 Correct 2 ms 568 KB Output is correct
16 Correct 2 ms 620 KB Output is correct
17 Correct 1 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 1 ms 356 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 2 ms 532 KB Output is correct
6 Correct 2 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 536 KB Output is correct
10 Correct 2 ms 548 KB Output is correct
11 Correct 2 ms 548 KB Output is correct
12 Correct 2 ms 552 KB Output is correct
13 Correct 2 ms 552 KB Output is correct
14 Correct 2 ms 568 KB Output is correct
15 Correct 2 ms 568 KB Output is correct
16 Correct 2 ms 620 KB Output is correct
17 Correct 1 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 748 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 1 ms 356 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 2 ms 532 KB Output is correct
6 Correct 2 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 536 KB Output is correct
10 Correct 2 ms 548 KB Output is correct
11 Correct 2 ms 548 KB Output is correct
12 Correct 2 ms 552 KB Output is correct
13 Correct 2 ms 552 KB Output is correct
14 Correct 2 ms 568 KB Output is correct
15 Correct 2 ms 568 KB Output is correct
16 Correct 2 ms 620 KB Output is correct
17 Correct 1 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 748 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 828 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 1 ms 356 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 2 ms 532 KB Output is correct
6 Correct 2 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 536 KB Output is correct
10 Correct 2 ms 548 KB Output is correct
11 Correct 2 ms 548 KB Output is correct
12 Correct 2 ms 552 KB Output is correct
13 Correct 2 ms 552 KB Output is correct
14 Correct 2 ms 568 KB Output is correct
15 Correct 2 ms 568 KB Output is correct
16 Correct 2 ms 620 KB Output is correct
17 Correct 1 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 748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -