Submission #1025091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025091		0npata	Roller Coaster Railroad (IOI16_railroad)	C++17	30 / 100	105 ms	17744 KiB

railroad

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

#define vec vector

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
	int n = s.size();

	vec<pair<int, int>> vs(n);
	vec<pair<int, int>> vt(n);

	for(int i = 0; i<n; i++) {
		vs[i] = {s[i], i};
		vt[i] = {t[i], i};
		//cerr << s[i] << ' ';
	}
	//ncerr << '\n';

	sort(vs.begin(), vs.end());
	sort(vt.begin(), vt.end());


	vec<pair<int, int>> se(0);

	if(vs[0].second == vt[n-1].second) {
		se.push_back({vs[0].second, vt[n-2].second});
		se.push_back({vs[1].second, vt[n-1].second});
	}
	else {
		se.push_back({vs[0].second, vt[n-1].second});
	}

	bool ans = false;
	for(auto [si, ei] : se) {
		int j = 0;
		set<int> reach;
		bool ok = true;
		for(int i = 0; i<n; i++) {
//			cerr << "----------------" << i << '\n';
			while(j<n && vt[j].first <=  vs[i].first) {
				if(vt[j].second != ei) {
					reach.insert(vt[j].second);
				}
//				cerr << vt[j].first << ": " << "shifting" << '\n';
				j++;
			}
			if(vs[i].second != si) {
				auto it = reach.begin();
				if(it == reach.end()) {
					ok = false;
					break;
				}
				if(*it == vs[i].second) it++;
				if(it == reach.end()) {
					ok = false;
					break;
				}
				reach.erase(it);
			}
//			cerr << bal << '\n';
		}

		ans |= ok;
	}

	if(ans) return 0;
	else return 1;
}

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