Submission #793239

#	Time	Username	Problem	Language	Result	Execution time	Memory
793239		prvocislo	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	90 ms	13556 KiB

railroad

#include "railroad.h"
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll inf = 1e18 + 5;
void upd(ll& a, ll b) { a = min(a, b); }
long long bruteforce(vector<int> s, vector<int> t) 
{
	int n = s.size();
	// slow
	vector<vector<ll> > dp((1 << n), vector<ll>(n, inf));
	for (int m = 0; m < (1 << n); m++)
	{
		if (!m)
		{
			for (int j = 0; j < n; j++) dp[(1 << j)][j] = 0;
			continue;
		}
		for (int i = 0; i < n; i++) if (m & (1 << i))
		{
			for (int j = 0; j < n; j++) if (!(m & (1 << j)))
			{
				ll di = max(0, t[i] - s[j]);
				upd(dp[m | (1 << j)][j], dp[m][i] + di);
			}
		}
	}
	return *min_element(dp.back().begin(), dp.back().end());
}
bool cmp(pair<int, int> a, pair<int, int> b)
{
	if (a.first != b.first) return a.first < b.first;
	return a.second > b.second;
}
vector<ll> b(60); // baza
bool add(ll x)
{
	for (ll i = b.size() - 1; i >= 0; i--) if (x & (1ll << i))
	{
		if (b[i]) x ^= b[i];
		else return b[i] = x, true; 
	}
	return false;
}
long long zero(vector<int> s, vector<int> t) // >= 0 budu vystupy, < 0 budu vstupy
{
	b.assign(60, 0);
	int n = s.size();
	vector<pair<int, int> > v;
	v.push_back({ 1, 0 });
	for (int i = 0; i < n; i++) v.push_back({ s[i], -i - 1 }), v.push_back({ t[i], i + 1 });
	sort(v.begin(), v.end(), cmp);

	vector<ll> val(n + 1, 0);
	for (int i = 0; i <= n; i++) val[i] = uniform_int_distribution<ll>(0, (1ll << 60ll) - 1ll)(rng);
	ll pf = 0;
	int in = 0, ou = 0;

	for (pair<int, int> p : v)
	{
		if (p.second >= 0) ou++;
		else in++;
		if (ou < in) return 1;
		pf ^= val[abs(p.second)];
		if (ou == in)
		{
			if (!add(pf)) return 1;
			pf = 0;
		}
	}
	return 0;
}
long long plan_roller_coaster(vector<int> s, vector<int> t)
{
    if (s.size() <= 16) return bruteforce(s, t);
	return zero(s, t);
}

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