제출 #522088

#제출 시각아이디문제언어결과실행 시간메모리
522088tabrHandcrafted Gift (IOI20_gift)C++17
10 / 100
166 ms30948 KiB
#include <bits/stdc++.h> using namespace std; #ifdef tabr #include "library/debug.cpp" #else #define debug(...) #endif #ifdef tabr void craft(string s); #else #include "gift.h" #endif struct dsu { vector<int> p; vector<int> sz; int n; dsu(int _n) : n(_n) { p = vector<int>(n); iota(p.begin(), p.end(), 0); sz = vector<int>(n, 1); } inline int get(int x) { if (p[x] == x) { return x; } else { return p[x] = get(p[x]); } } inline bool unite(int x, int y) { x = get(x); y = get(y); if (x == y) { return false; } p[x] = y; sz[y] += sz[x]; return true; } inline bool same(int x, int y) { return (get(x) == get(y)); } inline int size(int x) { return sz[get(x)]; } inline bool root(int x) { return (x == get(x)); } }; int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) { dsu uf(n); vector<int> c(n + 1); for (int i = 0; i < r; i++) { if (x[i] == 2) { continue; } c[a[i]]++; c[b[i]]--; } for (int i = 0; i < n; i++) { c[i + 1] += c[i]; if (c[i]) { uf.unite(i, i + 1); } } string ans(n, '?'); ans[0] = 'R'; c = vector<int>(n + 1); for (int i = 1; i < n; i++) { if (uf.same(i, i - 1)) { ans[i] = ans[i - 1]; } else { ans[i] = ans[i - 1] ^ 'R' ^ 'B'; c[i - 1] = 1; } } for (int i = 0; i < n; i++) { c[i + 1] += c[i]; } for (int i = 0; i < r; i++) { if (x[i] == 1) { continue; } if (c[a[i]] >= c[b[i] - 1]) { return 0; } } craft(ans); return 1; } #ifdef tabr int main() { ios::sync_with_stdio(false); cin.tie(0); return 0; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...