oj.uz

Submission #249907

# Submission time Handle Problem Language Result Execution time Memory
249907 2020-07-16T12:06:38 Z kostia244 Ancient Books (IOI17_books) C++17
0 / 100
 18 ms 29056 KB 
#include "books.h"
#include<bits/extc++.h>
using namespace std;
const int maxn = 1<<20;
using ll = long long;
int vis[maxn], a[maxn], col[maxn], n, id = 0;
vector<int> cycle[maxn];
ll ans = 0;
vector<array<int, 2>> segs;
void touch(int p) {
	if(vis[p]) return;
	++id;
	int l = p, r = p, lst = p;
	while(!vis[p]) {
		vis[p] = 1;
		l = min(l, p);
		r = max(r, p);
		
		col[p] = id;
		
		lst = p;
		p = a[p];
		ans += abs(p-lst);
	}
}
int L, R, pL, pR;
void upd(int i) {
	pL = min(pL, cycle[col[i]][0]);
	pR = max(pR, cycle[col[i]].back());
}
void expand() {
	while(pL < L || pR > R) {
		while(L > pL) upd(--L);
		while(R < pR) upd(++R);
	}
}
template<int fl>
pair<int, int> find() {
	int bl = L, br = R, cost = 0;
	//cout << fl << "::\n";
	//cout << cost << " " << L << " " << R << " TO " << endl;
	while((L == bl || R == br) && (fl ? L : R+1!=n)) {
		fl ? --pL : ++pR;
		//cout << L << " " << R << " " << bl << " " << br << endl;
		++cost;
		expand();
	}
	//cout << cost << " " << L << " " << R << endl;
	int nl = L, nr = R;
	pL = L = bl, R = pR = br;
	if(L == nl || R == nr) return {1<<30, -1};
	return {cost, fl ? nl : nr};
}
ll minimum_walk(vector<int> _a, int s) {
	n = _a.size();
	for(int i = 0; i < n; i++) a[i] = _a[i];
	for(int i = 0; i < n; i++) {
		touch(i);
	}
	for(int i = 0; i < n; i++) cycle[col[i]].push_back(i);
	memset(vis, 0, sizeof vis);
	ll tans = 0;
	pL = pR = R = s, L = s+1;
	expand();
	while(true) {
		auto [lcst, lp] = find<1>();
		auto [rcst, rp] = find<0>();
		//cout << pL << " " << pR << endl;
		if(lp == -1 && rp == -1) break;
		if(lcst < rcst) pL = lp;
		else pR = rp;
		ans += 2*min(lcst, rcst);
		expand();
	}
	return ans;
}

Compilation message

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:62:5: warning: unused variable 'tans' [-Wunused-variable]
  ll tans = 0;
     ^~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 29056 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 29056 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 29056 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 29056 KB Output is correct
2 Correct 16 ms 29056 KB Output is correct
3 Correct 17 ms 29056 KB Output is correct
4 Incorrect 18 ms 29056 KB 3rd lines differ - on the 1st token, expected: '2094', found: '818'
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 29056 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -