#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);
}
/*
Further update: this greedy algorithm is pretty much outright wrong.
We could think like this: Whenever we connect the end of track i with the beginning of track j, we are essentially creating an edge
from vertex i to vertex j, if we're thinking abouut the set of tracks as vertices on a graph.
The resulting "graph" of a valid track allocation should be either a "chain"/line/whatever, or a singular cycle. This kind of greedy
assignment wouldn't always result in a valid graph.
THe created graph is only guaranteed to be a graph with n vertices, n/n-1 edges, and each vertex only have an in and out degree of 0 or 1.
Basically, it could create a graph with several cycles and a chain, instead of a singular chain or a singular cycle. Take this test as
an example:
5
2 11
8 3
4 7
10 5
6 9
(stolen from Codeforces).
Ideally, the track allocation should be a permutation of (1,2,3,4,5). However, whatever tf you do, this greedy algorithm would result in
2 cycles (2=>3,3=>2), (4=>5,5=>4) and the 1st track is left alone. Turns out the test for this problem is shitty, lmao. Imagine passing
with a wrong greedy algorithm. They should've seen it coming tbh.
.......30 free pts in something this hard is still funny doe. This *is* a shitty greedy, after all
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
n = 2 |
| 2 |
Correct |
0 ms |
348 KB |
n = 2 |
| 3 |
Correct |
0 ms |
344 KB |
n = 2 |
| 4 |
Correct |
0 ms |
348 KB |
n = 2 |
| 5 |
Correct |
0 ms |
344 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 |
348 KB |
n = 2 |
| 2 |
Correct |
0 ms |
348 KB |
n = 2 |
| 3 |
Correct |
0 ms |
344 KB |
n = 2 |
| 4 |
Correct |
0 ms |
348 KB |
n = 2 |
| 5 |
Correct |
0 ms |
344 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 |
66 ms |
6924 KB |
n = 199999 |
| 2 |
Correct |
74 ms |
10784 KB |
n = 199991 |
| 3 |
Correct |
65 ms |
10552 KB |
n = 199993 |
| 4 |
Correct |
49 ms |
8644 KB |
n = 152076 |
| 5 |
Correct |
30 ms |
5328 KB |
n = 93249 |
| 6 |
Correct |
62 ms |
9664 KB |
n = 199910 |
| 7 |
Correct |
63 ms |
9916 KB |
n = 199999 |
| 8 |
Correct |
61 ms |
9656 KB |
n = 199997 |
| 9 |
Correct |
60 ms |
9672 KB |
n = 171294 |
| 10 |
Correct |
46 ms |
8672 KB |
n = 140872 |
| 11 |
Correct |
61 ms |
9656 KB |
n = 199886 |
| 12 |
Correct |
62 ms |
10040 KB |
n = 199996 |
| 13 |
Correct |
62 ms |
9764 KB |
n = 200000 |
| 14 |
Correct |
65 ms |
10032 KB |
n = 199998 |
| 15 |
Correct |
61 ms |
9900 KB |
n = 200000 |
| 16 |
Correct |
63 ms |
10304 KB |
n = 199998 |
| 17 |
Correct |
63 ms |
10684 KB |
n = 200000 |
| 18 |
Correct |
62 ms |
10208 KB |
n = 190000 |
| 19 |
Correct |
60 ms |
10056 KB |
n = 177777 |
| 20 |
Correct |
32 ms |
5548 KB |
n = 100000 |
| 21 |
Correct |
65 ms |
10792 KB |
n = 200000 |
| 22 |
Correct |
64 ms |
10688 KB |
n = 200000 |
| 23 |
Correct |
71 ms |
10928 KB |
n = 200000 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
n = 2 |
| 2 |
Correct |
0 ms |
348 KB |
n = 2 |
| 3 |
Correct |
0 ms |
344 KB |
n = 2 |
| 4 |
Correct |
0 ms |
348 KB |
n = 2 |
| 5 |
Correct |
0 ms |
344 KB |
n = 2 |
| 6 |
Incorrect |
0 ms |
348 KB |
answer is not correct: 1 instead of 523688153 |
| 7 |
Halted |
0 ms |
0 KB |
- |
