oj.uz

Submission #299025

# Submission time Handle Problem Language Result Execution time Memory
299025 2020-09-14T12:19:18 Z keko37 Ancient Books (IOI17_books) C++14
0 / 100
 2000 ms 384 KB 
#include<bits/stdc++.h>
#include "books.h"

using namespace std;

typedef long long llint;
typedef vector <int> vi;
typedef pair <int, int> pi;

const int MAXN = 1000005;

llint n, s, sol, cnt;
int curr_lef, curr_rig, lim_lef, lim_rig, edge_lef = -1, edge_rig = -1;
int p[MAXN], ok_pref[MAXN], ok_suf[MAXN];
int bio[MAXN], lo[MAXN], hi[MAXN];

void precompute_ok () {
	for (int i = 0; i < n; i++) {
		if (i > 0) ok_pref[i] |= ok_pref[i - 1];
		if (i != p[i]) ok_pref[i] = 1;
		if (ok_pref[i] == 1 && edge_lef == -1) edge_lef = i;
	}
	for (int i = n-1; i >= 0; i--) {
		if (i + 1 < n) ok_suf[i] |= ok_suf[i + 1];
		if (i != p[i]) ok_suf[i] = 1;
		if (ok_suf[i] == 1 && edge_rig == -1) edge_rig = i;
	}
	while (ok_pref[s] == 0) s++, sol++;
	while (ok_suf[s] == 0) s--, sol++;	
}

void dfs (int x) {
	bio[x] = cnt;
	lo[cnt] = min(lo[cnt], x);
	hi[cnt] = max(hi[cnt], x);
	if (bio[p[x]] == 0) dfs(p[x]);
}

void find_cycles () {
	for (int i = 0; i < n; i++) {
		if (bio[i] == 0) {
			cnt++;
			lo[cnt] = 1e9; hi[cnt] = -1e9;
			dfs(i);
		}
	}
}

void update () {
	while (curr_lef != lim_lef && curr_rig != lim_rig) {
		if (curr_lef != lim_lef) {
			curr_lef--;
			lim_lef = min(lim_lef, lo[bio[curr_lef]]);
			lim_rig = max(lim_rig, hi[bio[curr_lef]]);
		} else if (curr_rig != lim_rig) {
			curr_rig++;
			lim_lef = min(lim_lef, lo[bio[curr_rig]]);
			lim_rig = max(lim_rig, hi[bio[curr_rig]]);
		}
	}
}

pi cost_lef (int lef, int rig) {
	int res = 0;
	int lim = lef;
	while (1) {
		if (lef == lim) {
			if (lef == edge_lef) return {edge_lef - 1, res};
			lef--; res++;
			if (hi[bio[lef]] > rig) return {lef, res};
			lim = min(lim, lo[bio[lef]]);
		} else {
			lef--;
			if (hi[bio[lef]] > rig) return {lef, res};
			lim = min(lim, lo[bio[lef]]);
		}
	}
}

pi cost_rig (int lef, int rig) {
	int res = 0;
	int lim = rig;
	while (1) {
		if (rig == lim) {
			if (rig == edge_rig) return {edge_rig + 1, res};
			rig++; res++;
			if (lo[bio[rig]] < lef) return {rig, res};
			lim = max(lim, hi[bio[rig]]);
		} else {
			rig++;
			if (lo[bio[rig]] < lef) return {rig, res};
			lim = max(lim, hi[bio[rig]]);
		}
	}
}

void solve () {
	while (1) {
		pi clef = cost_lef(curr_lef, curr_rig);
		pi crig = cost_rig(curr_lef, curr_rig);
		if (clef.first < edge_lef || crig.first > edge_rig) {
			sol += clef.second + crig.second;
			break;
		}
		if (clef.second < crig.second) {
			sol += clef.second;
			lim_lef = clef.first;
			update();
		} else {
			sol += crig.second;
			lim_rig = crig.first;
			update();
		}
	}
}

llint minimum_walk (vi P, int S) {
	n = P.size(); s = S;
	bool same = 1;
	for (int i = 0; i < n; i++) {
		p[i] = P[i];
		if (p[i] != i) same = 0;
		sol += abs(i - p[i]);
	}
	if (same) return 0;
	precompute_ok();
	find_cycles();
	curr_lef = curr_rig = s;
	lim_lef = lo[bio[s]], lim_rig = hi[bio[s]];
	update();
	solve();
	return sol;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB 3rd lines differ - on the 1st token, expected: '6', found: '7'
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB 3rd lines differ - on the 1st token, expected: '6', found: '7'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB 3rd lines differ - on the 1st token, expected: '6', found: '7'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2081 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB 3rd lines differ - on the 1st token, expected: '6', found: '7'
3 Halted 0 ms 0 KB -