Submission #873573

# Submission time Handle Problem Language Result Execution time Memory
873573 2023-11-15T10:12:51 Z Lib Roller Coaster Railroad (IOI16_railroad) C++14
30 / 100
91 ms 6920 KB
#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;
int n;
vector <pair <int,int> > EnterSpeed;
vector <pair <int,int> > ExitSpeed;
long long plan_roller_coaster (vector <int> s, vector <int> t){
	n=s.size();
	EnterSpeed.clear();
	ExitSpeed.clear();
	/*
	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(),greater<pair <int,int> >());
	sort(ExitSpeed.begin(),ExitSpeed.end(),greater<pair <int,int> >());
	int ValidPairs=0;
	pair <int,int> temp;
	//Assigning track endpoints with new tracks
	while(!EnterSpeed.empty()&&!ExitSpeed.empty()&&ValidPairs<n-1){
		//Trying to match with the startpoint that isn't in the same track, and has the smallest entrance speed possible
		while(!EnterSpeed.empty()&&ExitSpeed.back().first>EnterSpeed.back().first){
			EnterSpeed.pop_back();
		}
		//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.back().second!=EnterSpeed.back().second){
			ValidPairs++;
			EnterSpeed.pop_back();
			ExitSpeed.pop_back();
		}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.back();
			EnterSpeed.pop_back();
         	EnterSpeed.pop_back();
			ExitSpeed.pop_back();
			ValidPairs++;
			EnterSpeed.push_back(temp);
		}else{
          //If you can't find any other segment and ran into a conflict, all is lost and done. Stop the assigning 
          //process immediately and hope for the best
          break;
        }
	}
	//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);
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 2
2 Correct 0 ms 344 KB n = 2
3 Correct 0 ms 348 KB n = 2
4 Correct 0 ms 348 KB n = 2
5 Correct 0 ms 348 KB n = 2
6 Incorrect 0 ms 348 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 2
2 Correct 0 ms 344 KB n = 2
3 Correct 0 ms 348 KB n = 2
4 Correct 0 ms 348 KB n = 2
5 Correct 0 ms 348 KB n = 2
6 Incorrect 0 ms 348 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 65 ms 6916 KB n = 199999
2 Correct 81 ms 6752 KB n = 199991
3 Correct 64 ms 6704 KB n = 199993
4 Correct 50 ms 6088 KB n = 152076
5 Correct 29 ms 3608 KB n = 93249
6 Correct 62 ms 6852 KB n = 199910
7 Correct 76 ms 6848 KB n = 199999
8 Correct 66 ms 6724 KB n = 199997
9 Correct 74 ms 6336 KB n = 171294
10 Correct 46 ms 5764 KB n = 140872
11 Correct 85 ms 6720 KB n = 199886
12 Correct 63 ms 6848 KB n = 199996
13 Correct 65 ms 6856 KB n = 200000
14 Correct 64 ms 6720 KB n = 199998
15 Correct 65 ms 6916 KB n = 200000
16 Correct 75 ms 6916 KB n = 199998
17 Correct 79 ms 6848 KB n = 200000
18 Correct 85 ms 6480 KB n = 190000
19 Correct 77 ms 6276 KB n = 177777
20 Correct 34 ms 3792 KB n = 100000
21 Correct 91 ms 6916 KB n = 200000
22 Correct 65 ms 6844 KB n = 200000
23 Correct 72 ms 6920 KB n = 200000
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 2
2 Correct 0 ms 344 KB n = 2
3 Correct 0 ms 348 KB n = 2
4 Correct 0 ms 348 KB n = 2
5 Correct 0 ms 348 KB n = 2
6 Incorrect 0 ms 348 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -