제출 #782972

#제출 시각아이디문제언어결과실행 시간메모리
782972Elias건물 4 (JOI20_building4)C++17
100 / 100
202 ms68972 KiB
#ifndef _DEBUG #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #include <bits/stdc++.h> using namespace std; #define int long long #define all(x) (x).begin(), (x).end() template <class T> istream &operator>>(istream &in, vector<T> &a) { for (T &x : a) in >> x; return in; } template <class T> ostream &operator<<(ostream &out, const vector<T> &a) { for (T x : a) out << x << " "; out << "\n"; return out; } struct Range { int low, high; Range operator+(Range other) { if (low < 0) return other; if (other.low < 0) return *this; assert(max(low, other.low) <= min(high, other.high) + 1); return {min(low, other.low), max(high, other.high)}; } Range operator+(int x) { return {low + x, high + x}; } }; signed main() { cin.tie(0); ios_base::sync_with_stdio(false); int n; cin >> n; vector<int> a(2 * n); vector<int> b(2 * n); cin >> a >> b; vector<Range> rA(2 * n, {-1000000000, -1000000000}), rB(2 * n, {-1000000000, -1000000000}); rA[0] = {0, 0}; rB[0] = {1, 1}; for (int i = 1; i < n * 2; i++) { if (a[i] >= a[i - 1]) rA[i] = rA[i] + rA[i - 1]; if (a[i] >= b[i - 1]) rA[i] = rA[i] + rB[i - 1]; if (b[i] >= a[i - 1]) rB[i] = (rB[i] + rA[i - 1]); if (b[i] >= b[i - 1]) rB[i] = (rB[i] + rB[i - 1]); rB[i] = rB[i] + 1; } string out; int needed = n; int last_taken = 10000000000000; while (rA.size()) { if (needed >= rA.back().low && needed <= rA.back().high && a.back() <= last_taken) { out.push_back('A'); last_taken = a.back(); } else if (needed >= rB.back().low && needed <= rB.back().high && b.back() <= last_taken) { out.push_back('B'); last_taken = b.back(); needed--; } else { cout << -1; return 0; } rA.pop_back(); rB.pop_back(); a.pop_back(); b.pop_back(); } reverse(out.begin(), out.end()); cout << out; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...