#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = -1;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
multiset<pi> in, out;
bool bad;
pi findin(pi cur){
in.erase(in.find({cur.first,cur.second}));
auto it=in.lower_bound({cur.second,0});
if(it==in.end()){
bad=1;
return {-1,-1};
} else{
pi res=*it;
in.insert({cur.first,cur.second});
return res;
}
}
pi findout(pi cur){
out.erase(out.find({cur.second,cur.first}));
auto it=out.lower_bound({cur.first,inf});
assert(it!=out.begin());
auto pre=prev(it);
pi res=*pre;
out.insert({cur.second,cur.first});
return res;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
int n=s.size();
for(int i=0;i<n;i++){
in.insert({s[i],t[i]});
out.insert({t[i],s[i]});
}
while((int)out.size() > 1){
pi t=*out.begin();
pi pin=findin({t.second,t.first});
if(bad)return 1;
pi pout=findout({pin.first,pin.second});
swap(pout.first,pout.second);
//debug(pin.first,pin.second,pout.first,pout.second);
in.erase(in.find(pin));
in.erase(in.find(pout));
out.erase(out.find({pout.second,pout.first}));
out.erase(out.find({pin.second,pin.first}));
pi newtrack={pout.first,pin.second};
in.insert({newtrack.first,newtrack.second});
out.insert({newtrack.second,newtrack.first});
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
n = 2 |
| 2 |
Correct |
0 ms |
348 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 |
1 ms |
348 KB |
n = 2 |
| 2 |
Correct |
0 ms |
348 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 |
559 ms |
22408 KB |
n = 199999 |
| 2 |
Correct |
501 ms |
22100 KB |
n = 199991 |
| 3 |
Correct |
384 ms |
22344 KB |
n = 199993 |
| 4 |
Correct |
388 ms |
16840 KB |
n = 152076 |
| 5 |
Correct |
172 ms |
10576 KB |
n = 93249 |
| 6 |
Correct |
351 ms |
22340 KB |
n = 199910 |
| 7 |
Correct |
295 ms |
25428 KB |
n = 199999 |
| 8 |
Correct |
258 ms |
24988 KB |
n = 199997 |
| 9 |
Correct |
381 ms |
22352 KB |
n = 171294 |
| 10 |
Correct |
287 ms |
18524 KB |
n = 140872 |
| 11 |
Correct |
297 ms |
25040 KB |
n = 199886 |
| 12 |
Correct |
290 ms |
25580 KB |
n = 199996 |
| 13 |
Correct |
291 ms |
25172 KB |
n = 200000 |
| 14 |
Correct |
249 ms |
25644 KB |
n = 199998 |
| 15 |
Correct |
252 ms |
25288 KB |
n = 200000 |
| 16 |
Correct |
266 ms |
25676 KB |
n = 199998 |
| 17 |
Correct |
157 ms |
26180 KB |
n = 200000 |
| 18 |
Correct |
302 ms |
24812 KB |
n = 190000 |
| 19 |
Correct |
228 ms |
23380 KB |
n = 177777 |
| 20 |
Incorrect |
134 ms |
13236 KB |
answer is not correct: 1 instead of 0 |
| 21 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
n = 2 |
| 2 |
Correct |
0 ms |
348 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 |
- |
