# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
198302 | 2020-01-25T13:25:10 Z | MiricaMatei | Santa Claus (RMI19_santa) | C++14 | 293 ms | 10616 KB |
#include <bits/stdc++.h> using namespace std; const int MAXN = 100000; struct Cadou { int p, val, pt; bool operator <(const Cadou& other) const { if (val == other.val) return p < other.p; return val < other.val; } }cd[MAXN], cp[MAXN]; int x[MAXN], h[MAXN], v[MAXN]; void solve() { int n, cad = 0, cop = 0; scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &x[i]); for (int i = 1; i <= n; ++i) scanf("%d", &h[i]); int lst = 0; for (int i = 1; i <= n; ++i) { scanf("%d", &v[i]); if (!h[i]) cd[++cad] = {x[i], v[i], 0}, lst = i; } sort(cd + 1, cd + cad + 1); multiset<int>s; int j = 1, l1 = 1; for (int i = 1; i <= n && j <= cad; ++i) { if (h[i] == 1) { s.insert(v[i]); cp[++cop] = {x[i], v[i], 0}; } while (j <= cad && !s.empty() && (*s.begin()) <= cd[j].val) { j++; s.erase(s.begin()); } l1 = i; } if (j <= cad) { for (int i = 1; i <= n; ++i) printf("-1 "); printf("\n"); return ; } lst = max(l1, lst); sort(cp + 1, cp + cop + 1); set<int>pq; int i1 = 1; j = 1; multiset<pair<int, int> >s1; while (j <= cad) { while (i1 <= cop && cp[i1].val <= cd[j].val) { pq.insert(cp[i1].p); i1++; } set<int>::iterator it = pq.lower_bound(cd[j].p); if (it == pq.end()) it--; cd[j].pt = (*it); if (cd[j].pt < cd[j].p) s1.insert({cd[j].pt, cd[j].val}); pq.erase(it); j++; } for (int i = 1; i < lst; ++i) printf("-1 "); if (lst <= n) { if (s1.empty()) { printf("%d ", x[lst]); } else { printf("%d ", 2 * x[lst] - (*s1.begin()).first); } } for (int i = lst + 1; i <= n; ++i) { if (h[i] == 1) { if (!s1.empty()) { pair<int, int>aux = *s1.begin(); if (aux.second >= v[i]) s1.erase(s1.begin()); } } if (s1.empty()) { printf("%d ", x[i]); } else { printf("%d ", 2 * x[i] - (*s1.begin()).first); } } printf("\n"); } int main() { int t; scanf("%d", &t); while (t--) solve(); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 376 KB | Output isn't correct |
2 | Incorrect | 3 ms | 376 KB | Output isn't correct |
3 | Incorrect | 9 ms | 504 KB | Output isn't correct |
4 | Incorrect | 17 ms | 888 KB | Output isn't correct |
5 | Incorrect | 35 ms | 1400 KB | Output isn't correct |
6 | Incorrect | 56 ms | 2296 KB | Output isn't correct |
7 | Incorrect | 100 ms | 3832 KB | Output isn't correct |
8 | Incorrect | 159 ms | 5724 KB | Output isn't correct |
9 | Incorrect | 202 ms | 7648 KB | Output isn't correct |
10 | Incorrect | 293 ms | 10616 KB | Output isn't correct |