# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
492934 | 2021-12-09T19:36:41 Z | kevin | Roller Coaster Railroad (IOI16_railroad) | C++17 | 275 ms | 31908 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long #define all(x) x.begin(), x.end() #define f first #define s second #define ca(v) for(auto i:v) cout<<i<<" "; #define nl cout<<"\n" const int MAXN = 5e5 + 5; ll plan_roller_coaster(vector<int> s, vector<int> t){ int N = s.size(); unordered_map<int, int> hsh; vector<int> cmp; for(int i=0; i<N; i++) { cmp.push_back(s[i]); cmp.push_back(t[i]); } sort(all(cmp)); cmp.resize(unique(all(cmp)) - cmp.begin()); for(int i=0; i<cmp.size(); i++) hsh[cmp[i]] = i; vector<int> in(cmp.size(), 0); vector<int> out(cmp.size(), 0); // update all the outs for(int i=0; i<N; i++) out[hsh[s[i]]]++; // greedily assign right arrows vector<int> rgt; for(int i=0; i<N; i++) rgt.push_back(hsh[t[i]]); sort(all(rgt)); int p = 0; for(int i:rgt){ while(p<N && (p < i || out[p] == in[p])) p++; if(p<N){ in[p]++; } } int cntl = 0; int cntg = 0; for(int i=0; i<cmp.size(); i++){ if(in[i] > out[i]) cntl += in[i] - out[i]; if(out[i] > in[i]) cntg += out[i] - in[i]; } if((cntl == 1 && cntg == 1) || (cntl + cntg == 0)) return 0; return 1; } // int main() // { // ios_base::sync_with_stdio(0); cin.tie(0); // if (fopen("input.in", "r")) freopen("input.in", "r", stdin); // }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 292 KB | answer is not correct: 1 instead of 0 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 292 KB | answer is not correct: 1 instead of 0 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 275 ms | 31908 KB | answer is not correct: 1 instead of 0 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 292 KB | answer is not correct: 1 instead of 0 |
2 | Halted | 0 ms | 0 KB | - |