Submission #112343

#	Time	Username	Problem	Language	Result	Execution time	Memory
112343		updown1	Ancient Books (IOI17_books)	C++17	50 / 100	354 ms	86520 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
//#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN = 1000000;
//Global Variables
ll N, out = 0, loc[MAXN], comp[MAXN], at = 0;
///             element ,   element
pair<int, int> rng[MAXN];
///                comp
vector<pair<int, int> > rng2;
bool vis[MAXN];
///   element ,     comp
vector<int> elements[MAXN];

void go1(int at, int co) {
	if (comp[at] != -1) return;
	rng[co].a = min(rng[co].a, at);
	rng[co].b = max(rng[co].b, at);
	comp[at] = -2;
	elements[co].pb(at);
	out += abs(loc[at]-at);
	go1(loc[at], co);
}
void go(int at) {
	if (vis[at]) return;
	vis[at] = true;
	go(loc[at]);
}
void chg(int a, int b) {
    for (int i: elements[a]) comp[i] = b;
}

ll minimum_walk(vector<int> p, int s) {
	N = p.size();
	ffi {rng[i] = mp(N, -1); comp[i] = -1; loc[i] = p[i];}
	ffi if (comp[i] == -1) {
		go1(i, at);
		at++;
	}
	//w<< "from components: " << out<<e;
	sort(rng, rng+at);
	For (i, 0, at) {
	    /// only one element - delete
	    if (rng[i].a == rng[i].b) continue;
	    /// vector is empty
	    if (rng2.empty()) {
            rng2.pb(rng[i]);
            chg(i, 0);
            continue;
	    }
        /// fully emcompassed - delete
        /// intersect - combine
        if (rng[i].a < rng2.back().b && rng2.back().b < rng[i].b) {
            chg(i, rng2.size()-1);
            rng2.back().b = rng[i].b;
        }
        /// don't intersect
        if (rng2.back().b < rng[i].a) {
            chg(i, rng2.size());
            rng2.pb(rng[i]);
        }
	}
	at = rng2.size();
	For (i, 0, at) {
	    rng[i] = rng2[i];
	    //w<< rng[i].a << " " << rng[i].b<<e;
	}

	bool moved = false;
	int far = s;
	if (comp[s] != -2) far = rng[comp[s]].b;
	For (i, 0, at) if (rng[i].a > s) {
	    out += 2*(rng[i].a - far);
        moved = true;
		far = rng[i].b;
	}
	far = s;
	if (comp[s] != -2) far = rng[comp[s]].a;
	for (int i=at-1; i>=0; i--) if (rng[i].b < s) {
        out += 2*(far - rng[i].b);
        moved = true;
	    far = rng[i].a;
		//w<< out<<e;
	}
	//w<< "moved: " << moved c out<<e;
	if (moved) return out;
	/// find closest location to s that isn't deleted
	int dist = N+1;
	ffi if (comp[i] != -2) {
        dist = min(dist, abs(s-i));
	}
	//w<< "dist: " << dist<<e;
	if (dist == N+1) dist = 0;
	//w<< "dist: " << dist<<e;
	return out + 2*dist;
}

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