Submission #282583

#	Time	Username	Problem	Language	Result	Execution time	Memory
282583		Noam13	Ancient Books (IOI17_books)	C++14	100 / 100	943 ms	148392 KiB

books

#include "books.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define vvb vector<vb>
#define ii pair<int, int>
#define x first
#define y second
#define vii vector<ii>
#define pb push_back
#define all(x) x.begin(), x.end()
#define loop(i,s,e) for(int i=s;i<e;++i)
#define chkmax(a,b) a = max(a,b)
#define chkmin(a,b) a = min(a,b)
using namespace std;
const int INF = 1e9;
typedef long long ll;

struct DSU{
	int n;
	vi p, sz;
	DSU(int n):n(n), p(n,-1), sz(n,1){}
	int find(int c){
		if (p[c]==-1) return c;
		return p[c] = find(p[c]);
	}
	void uni(int a, int b){
		a = find(a), b = find(b);
		if (a==b) return  ;
		if (sz[a]>sz[b]) swap(a,b);
		p[a] = b;
		sz[b] += sz[a];
	}
};
ll minimum_walk(vi p, int s) {
	ll ans = 0;
	int n = p.size();
	vb check(n,0);
	int needl = s, needr = s;
	vi v1(n), v2(n);
	loop(i,0,n) if(!check[i]){
		vi vec;
		int mn = i, mx = i;
		for(int cur = i;!check[cur]; cur = p[cur]){
			check[cur] = 1;
			ans+=abs(cur-p[cur]);
			vec.pb(cur);
			chkmin(mn, cur); chkmax(mx, cur);
		}
		if (vec.size()>1) chkmax(needr, mx), chkmin(needl, mn);
		for(auto x:vec) v2[x] = mx, v1[x] = mn;
	}
	int l = s, r = s, ml=s, mr=s;
	while(l>=ml || r<=mr){
		if (l>=ml){
			chkmax(mr, v2[l]);
			chkmin(ml, v1[l]);
			l--;
		}
		else{
			chkmax(mr, v2[r]);
			chkmin(ml, v1[r]);
			r++;
		}
	}
	vi right(1,l+1), left(1,r-1);
	vi comp(n,0); int cnt = 0;
	while(r<n){
		if (r>mr) right.pb(n), mr++, cnt++;
		comp[r] = cnt;
		chkmax(mr, v2[r]); 
		chkmin(right.back(), v1[r]);
		r++;
	}
	cnt = 0;
	while(l>=0){
		if (l<ml) left.pb(-1), ml--, cnt++;
		comp[l] = cnt;
		chkmin(ml, v1[l]); 
		chkmax(left.back(), v2[l]);
		l--;
	}
	int a = left.size(), b = right.size();
	for(int &x:left) x = comp[x] + (x>s?a:0);
	for(int &x:right) x = comp[x] + (x>s?a:0);
	needl = comp[needl], needr = comp[needr];
	DSU dsu(a+b);
	dsu.uni(0,a); //same one
	loop(i,0,a) dsu.uni(i, left[i]);
	loop(i,0,b) dsu.uni(i+a, right[i]);
	map<int, int> conv; int tmp=0;
	loop(i,0,a+b) if(dsu.p[i]==-1) conv[i]=tmp++;
	vvi g(tmp);
	auto get = [&](int i){
		return conv[dsu.find(i)];
	};
	loop(i,0,a-1){
		int aa = get(i), bb = get(i+1);
		if (aa!=bb) g[aa].pb(bb);
	}
	loop(i,0,b-1){
		int aa = get(i+a), bb = get(i+a+1);
		if (aa!=bb) g[aa].pb(bb);
	}	
	vi vals(tmp);
	loop(i,0,a) vals[get(i)]|=1; 
	loop(i,0,b) vals[get(i+a)]|=2;
	//one that has 3 is both
	needl = get(needl), needr = get(needr+a); //updating targets
	queue<int> q; q.push(get(0));
	vi dist(tmp,-1); dist[get(0)] = 0;
	int has = 0, lasty = 0, lasth=0;
	//cout<<"AB: "<<a<<" "<<b<<" "<<ans<<endl;
	while(q.size()){
		int cur = q.front(); q.pop();
		if (vals[cur]==3) lasty = dist[cur];
		if (cur==needl) ans+=2*dist[cur], has|=1;
		if (cur==needr) ans+=2*dist[cur], has|=2;
		//cout<<"CUR: "<<cur<<" "<<dist[cur]<<endl;
		if (has!=0 && lasth==0){
			ans-=2*lasty;
		}
		if (has==3) break;
		lasth = has;
		for(auto nei:g[cur]) if(dist[nei]==-1){
			dist[nei]=dist[cur]+1;
			q.push(nei);
		}
	}
	return ans;
}
/*
clear
g++ books.cpp grader.cpp -o a ; ./a
4 0
0 2 3 1

11 2
10 5 2 4 3 8 7 6 1 9 0

4 1 3 2 7 6 5 0
*/

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 30 / 30