제출 #1025043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1025043		0npata	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	60 ms	10020 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});
	//k}

	bool ans = false;
	for(auto [si, ei] : se) {
		int j = 0;
		int bal = 0;
		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) bal++;
//				cerr << vt[j].first << ": " << "shifting" << '\n';
				j++;
			}
			if(vs[i].second != si) bal--;
//			cerr << bal << '\n';
			if(bal < 0) {
				ok = false;
				break;
			}
		}

		ans |= ok;
	}

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

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