Submission #302221

#	Time	Username	Problem	Language	Result	Execution time	Memory
302221		JPN20	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	213 ms	17120 KiB

railroad

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

// Input
long long N;
long long S[1 << 18], T[1 << 18];

// Solutions
bool used[1 << 18];
long long idx[1 << 18];
long long dp[1 << 16][16];

bool calc(int stt, int goa) {
	// SORTS
	vector<pair<int, int>> vec;
	for (int i = 0; i < N; i++) {
		if (i == stt) continue;
		int pos1 = lower_bound(T, T + N, S[i] + 1) - T; if (goa < pos1) pos1--;
		int pos2 = i; if (goa < pos2) pos2--; if (i == goa) pos2 = -1;
		vec.push_back(make_pair(pos1, pos2));
	}
	sort(vec.begin(), vec.end());
	
	// PRCLC
	for (int i = 0; i < N; i++) used[i] = false;
	for (int i = 0; i < N; i++) idx[i] = -1;
	for (int i = 0; i < vec.size(); i++) {
		if (vec[i].second != -1) idx[vec[i].second] = i;
	}
	
	// CALCS
	int pres = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
	for (int i = 0; i < (int)vec.size(); i++) {
		for (int j = pres; j < vec[i].first; j++) {
			if (idx[j] < i) Q.push(make_pair(1000000007, j));
			if (idx[j] > i) Q.push(make_pair(idx[j], j));
		}
		pres = vec[i].first;
		while (!Q.empty()) {
			int r = Q.top().first; if (r == i) Q.pop();
			else break;
		}
		if (Q.empty()) return false;
		int r = Q.top().second;
		used[r] = true; Q.pop();
		if (vec[i].second != -1 && used[vec[i].second] == false) Q.push(make_pair(1000000007, i));
	}
	return true;
}

long long solve_subtask3() {
	// SORTS
	vector<pair<long long, long long>> vec;
	for (int i = 0; i < N; i++) vec.push_back(make_pair(T[i], S[i]));
	sort(vec.begin(), vec.end());
	for (int i = 0; i < N; i++) T[i] = vec[i].first;
	for (int i = 0; i < N; i++) S[i] = vec[i].second;
	
	// PRCLC
	vector<pair<int, int>> vecs;
	for (int i = 0; i < N; i++) vecs.push_back(make_pair(S[i], i));
	sort(vecs.begin(), vecs.end());
	
	// FINAL
	vector<int> u;
	vector<int> v;
	for (int i = 0; i < min(7LL, N); i++) u.push_back(vecs[i].second);
	for (int i = 0; i < min(7LL, N); i++) v.push_back(N - 1 - i);
	for (int i = 0; i < u.size(); i++) {
		for (int j = 0; j < v.size(); j++) {
			if (u[i] == v[j]) continue;
			if (calc(u[i], v[j]) == true) return 0;
		}
	}
	return 1000000007LL;
}

long long solve_subtask2() {
	// PRCLC
	for (int i = 0; i < (1 << N); i++) {
		for (int j = 0; j < N; j++) dp[i][j] = (1LL << 60);
	}
	for (int i = 0; i < N; i++) dp[1 << i][i] = 0;
	
	// CALC
	for (int i = 0; i < (1 << N); i++) {
		for (int j = 0; j < N; j++) {
			if (dp[i][j] == (1LL << 60)) continue;
			for (int k = 0; k < N; k++) {
				if ((i / (1 << k)) % 2 == 1) continue;
				long long cost = max(0LL, T[j] - S[k]);
				dp[i + (1 << k)][k] = min(dp[i + (1 << k)][k], dp[i][j] + cost);
			}
		}
	}
	
	// FINAL
	long long Answer = (1LL << 60);
	for (int i = 0; i < N; i++) Answer = min(Answer, dp[(1 << N) - 1][i]);
	return Answer;
}

int cnts = 0;

long long plan_roller_coaster(vector<int> s, vector<int> t) {
	N = s.size();
	for (int i = 0; i < N; i++) S[i] = s[i];
	for (int i = 0; i < N; i++) T[i] = t[i];
	cnts += 1;
	
	if (N <= 16) return solve_subtask2();
	return solve_subtask3();
}

Compilation message (stderr)

railroad.cpp: In function 'bool calc(int, int)':
railroad.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for (int i = 0; i < vec.size(); i++) {
      |                  ~~^~~~~~~~~~~~
railroad.cpp: In function 'long long int solve_subtask3()':
railroad.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for (int i = 0; i < u.size(); i++) {
      |                  ~~^~~~~~~~~~
railroad.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for (int j = 0; j < v.size(); j++) {
      |                   ~~^~~~~~~~~~

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