제출 #249907

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
249907		kostia244	고대 책들 (IOI17_books)	C++17	0 / 100	18 ms	29056 KiB

books

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30