# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
492942 | 2021-12-09T20:13:14 Z | kevin | Roller Coaster Railroad (IOI16_railroad) | C++17 | 294 ms | 31884 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]); } cmp.push_back(0); 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]]); rgt.push_back(0); sort(all(rgt)); int p = 1; for(int i:rgt){ while(p<cmp.size() && (p < i || out[p] == in[p])) p++; if(p<cmp.size()){ in[p]++; } } for(int i=1; i<cmp.size(); i++){ if(out[i] > in[i]) return 1; } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | n = 2 |
2 | Correct | 0 ms | 204 KB | n = 2 |
3 | Correct | 0 ms | 204 KB | n = 2 |
4 | Correct | 0 ms | 292 KB | n = 2 |
5 | Correct | 1 ms | 204 KB | n = 2 |
6 | Incorrect | 0 ms | 204 KB | answer is not correct: 1 instead of 523688153 |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | n = 2 |
2 | Correct | 0 ms | 204 KB | n = 2 |
3 | Correct | 0 ms | 204 KB | n = 2 |
4 | Correct | 0 ms | 292 KB | n = 2 |
5 | Correct | 1 ms | 204 KB | n = 2 |
6 | Incorrect | 0 ms | 204 KB | answer is not correct: 1 instead of 523688153 |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 293 ms | 28032 KB | n = 199999 |
2 | Correct | 294 ms | 31884 KB | n = 199991 |
3 | Correct | 287 ms | 31772 KB | n = 199993 |
4 | Correct | 188 ms | 22660 KB | n = 152076 |
5 | Correct | 101 ms | 15172 KB | n = 93249 |
6 | Correct | 192 ms | 25052 KB | n = 199910 |
7 | Correct | 271 ms | 30724 KB | n = 199999 |
8 | Correct | 197 ms | 25176 KB | n = 199997 |
9 | Correct | 222 ms | 25308 KB | n = 171294 |
10 | Correct | 173 ms | 21636 KB | n = 140872 |
11 | Incorrect | 189 ms | 25320 KB | answer is not correct: 0 instead of 1 |
12 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | n = 2 |
2 | Correct | 0 ms | 204 KB | n = 2 |
3 | Correct | 0 ms | 204 KB | n = 2 |
4 | Correct | 0 ms | 292 KB | n = 2 |
5 | Correct | 1 ms | 204 KB | n = 2 |
6 | Incorrect | 0 ms | 204 KB | answer is not correct: 1 instead of 523688153 |
7 | Halted | 0 ms | 0 KB | - |