Submission #464964

#	Time	Username	Problem	Language	Result	Execution time	Memory
464964		ace_in_the_hole	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	138 ms	13464 KiB

railroad

#include "railroad.h"

#include<bits/stdc++.h>
using namespace std;

typedef long long Int;
const int MOD = 2004010501; //MOD > 2e9

const Int INF = 1e18;
const int MAX = 2e5 + 100;
int num_elems;
Int s[MAX], t[MAX];
Int cost[20][20];
Int dp[1 << 16][16];
void minimize(Int& var, const Int& val) { if (val < var) var = val; }
/*
view each road as a graph node, then "railroads" are, in fact, just edges between nodes.
sort increasingly by s
*/

Int subtask2() {
	for (int i = 0; i < num_elems; i++) 
		for (int j = 0; j < num_elems; j++) cost[i][j] = max(0LL, t[i] - s[j]);
	for (int msk = 0; msk < (1 << num_elems); msk++)
		for (int pos = 0; pos < num_elems; pos++) dp[msk][pos] = INF;
	for (int i = 0; i < num_elems; i++) dp[1 << i][i] = 0;
	for (int msk = 0; msk < (1 << num_elems); msk++)
		for (int pos = 0; pos < num_elems; pos++) if (dp[msk][pos] < INF)
			for (int nxt = 0; nxt < num_elems; nxt++) if (((msk >> nxt) & 1) == 0)
				minimize(dp[msk | (1 << nxt)][nxt], dp[msk][pos] + cost[pos][nxt]);
	Int ans = INF;
	const int FULL = (1 << num_elems) - 1;
	for (int pos = 0; pos < num_elems; pos++)
		minimize(ans, dp[FULL][pos]);
	return ans;
}

pair<int,int> sections[MAX];
int pos[MAX], indices[MAX], list[MAX];
bool mark[MAX];
bool cmp(const int& i, const int& j) { return (pos[i] == pos[j]) ? i > j : pos[i] > pos[j]; }
int subtask3() {
	for (int i = 1; i <= num_elems; i++) sections[i] = make_pair(s[i], t[i]);
	sort(sections + 1, sections + 1 + num_elems);
	for (int i = 1; i <= num_elems; i++) {
		//min a, such that s[a] >= t[i]. If all all s[a] < t[i]?
		pos[i] = num_elems + 1;
		int lo = 1, hi = num_elems;
		while (lo <= hi) {
			int mid = (lo+hi) >> 1;
			if (sections[mid].first < sections[i].second) lo = mid + 1;
			else pos[i] = mid, hi = mid - 1;
		}
		indices[i] = i, ::list[i] = i;
	}
	sort(indices + 1, indices + 1 + num_elems, cmp);
	int last = num_elems, cnt_not_ok = 0;
	for (int j = 1; j <= num_elems; j++) {
		const int& i = indices[j];
		int sav = -1; bool found = false;
		for (;last >= pos[i] and !found; --last) {
			if (::list[last] == i) sav = last;
			if (!mark[::list[last]]) mark[::list[last]] = found = true;
		}
		if (!found) ++cnt_not_ok;
		if (cnt_not_ok > 1) return MOD;
		if (sav != -1) swap(::list[++last], ::list[sav]);
	}
	return 0;
}

Int solve()
{
  	if (num_elems <= 16) return subtask2(); 
	return subtask3();
}


long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    ::num_elems = (int) s.size();
	for (int i = 0; i < num_elems; i++) ::s[i] = s[i], ::t[i] = t[i];
    return solve();
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36