Submission #872996

#	Time	Username	Problem	Language	Result	Execution time	Memory
872996		Lib	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	2063 ms	10724 KiB

railroad

#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;
int n;
deque <pair <int,int> > EnterSpeed;
deque <pair <int,int> > ExitSpeed;
long long plan_roller_coaster (vector <int> s, vector <int> t){
	n=s.size();
	/*
	Subtask 1 and 2 is trival and basically not worth spending time for, so I'll skip it
	Of course, there exists a better solution to subtask 3 that is actually relevant to the full solution, but 30 points is 30 points,
	especially if that's from a shitty greedy solution
	*/
	
	/*
	If a finished track could be created without adding in any additional segments, this is the equivalent of: for all but 1 segment, there
	has to be a track segment that follows it.
	=> Just greedily assign exit speeds with corresponding entrance speeds that isn't from the same segment,
	if n-1 pairs (or more) could be formed, there exists an answer.
	Simple as that.
	*/
	for(int i=0;i<n;i++){
		EnterSpeed.push_back({s[i],i});
		ExitSpeed.push_back({t[i],i});
	}
	sort(EnterSpeed.begin(),EnterSpeed.end());
	sort(ExitSpeed.begin(),ExitSpeed.end());
	int ValidPairs=0;
	pair <int,int> temp;
	//Assigning track endpoints with new tracks
	while(!EnterSpeed.empty()){
		//Trying to match with the startpoint that isn't in the same track, and has the smallest entrance speed possible
		while(!EnterSpeed.empty()&&ExitSpeed.front().first>EnterSpeed.front().first){
			EnterSpeed.pop_front();
		}
		//It matches and doesn't belong to the same sector. Is valid, so increase the amount of matched pairs by 1
		if(!EnterSpeed.empty()&&ExitSpeed.front().second!=EnterSpeed.front().second){
			ValidPairs++;
			EnterSpeed.pop_front();
			ExitSpeed.pop_front();
		}else if(!EnterSpeed.size()>1){
			//It matches, but both of this startpoint and endpoint belongs in the same segment. Match it with the
			//next smallest unmatched entrance speed
			temp=EnterSpeed.front();
			EnterSpeed.pop_front();
			ValidPairs++;
			EnterSpeed.push_front(temp);
		}
	}
	//If at least N-1 pairs could be matched, there exists 1 valid rollercoaster using only the default tracks. Otherwise, no
	return (ValidPairs>=n-1);
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:41:30: warning: logical not is only applied to the left hand side of comparison [-Wlogical-not-parentheses]
   41 |   }else if(!EnterSpeed.size()>1){
      |                              ^
railroad.cpp:41:12: note: add parentheses around left hand side expression to silence this warning
   41 |   }else if(!EnterSpeed.size()>1){
      |            ^~~~~~~~~~~~~~~~~~
      |            (                 )
railroad.cpp:41:30: warning: comparison of constant '1' with boolean expression is always false [-Wbool-compare]
   41 |   }else if(!EnterSpeed.size()>1){
      |            ~~~~~~~~~~~~~~~~~~^~

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