제출 #719925

#제출 시각아이디문제언어결과실행 시간메모리
719925walterw건물 4 (JOI20_building4)C++17
0 / 100
2 ms468 KiB
#include "bits/stdc++.h" using namespace std; void abc() {cout << endl;} template <typename T, typename ...U> void abc(T a, U ...b) { cout << a << ' ', abc(b...); } template <typename T> void printv(T l, T r) { while (l != r) cout << *l << " \n"[++l == r]; } template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) { return o >> a.first >> a.second; } template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) { return o << '(' << a.first << ", " << a.second << ')'; } template <typename T> ostream& operator << (ostream& o, vector<T> a) { bool is = false; for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;} return o << '}'; } #ifdef local #define test(args...) abc("[" + string(#args) + "]", args) #else #define test(args...) void(0) #endif using ll = long long; ll dp[1000005][2][2]; int a[1000005], b[1000005]; string ans = ""; void retrieve(int pos, int col, int aleft) { if (pos == 1) { if (col == 0) ans += "A"; else ans += "B"; return; } if (col == 0) { ans += "A"; if (a[pos - 1] <= a[pos] && dp[pos - 1][0][0] <= (aleft - 1) && (aleft - 1) <= dp[pos - 1][0][1]) { retrieve(pos - 1, 0, aleft - 1); } else { retrieve(pos - 1, 1, aleft - 1); } } else { ans += "B"; if (a[pos - 1] <= b[pos] && dp[pos - 1][0][0] <= (aleft) && (aleft) <= dp[pos - 1][0][1]) { retrieve(pos - 1, 0, aleft); } else { retrieve(pos - 1, 1, aleft); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("", "r", stdin); // freopen("", "w", stdout); int n; cin >> n; for (int i = 1; i <= 2 * n; i++) cin >> a[i]; for (int i = 1; i <= 2 * n; i++) cin >> b[i]; for (int i = 1; i <= 2 * n; i++) { dp[i][0][0] = dp[i][1][0] = 1e16; dp[i][0][1] = dp[i][1][1] = -1; } dp[1][0][0] = 1; dp[1][0][1] = 1; dp[1][1][0] = 0; dp[1][1][1] = 0; for (int i = 2; i <= 2 * n; i++) { if (a[i - 1] <= a[i]) { dp[i][0][0] = min(dp[i][0][0], dp[i - 1][0][0] + 1); dp[i][0][1] = max(dp[i][0][1], dp[i - 1][0][1] + 1); } if (b[i - 1] <= a[i]) { dp[i][0][0] = min(dp[i][0][0], dp[i - 1][1][0] + 1); dp[i][0][1] = max(dp[i][0][1], dp[i - 1][1][1] + 1); } if (a[i-1] <= b[i]) { dp[i][1][0] = min(dp[i][1][0], dp[i-1][0][0]); dp[i][1][1] = max(dp[i][1][1], dp[i-1][0][1]); } if (b[i-1] <= b[i]) { dp[i][1][0] = min(dp[i][1][0], dp[i-1][1][0]); dp[i][1][1] = max(dp[i][1][1], dp[i-1][1][1]); } } if ((dp[2 * n][0][0] <= n && dp[2 * n][0][1] >= n)) { retrieve(2 * n, 0, n); reverse(ans.begin(), ans.end()); cout << ans; } else if ((dp[2 * n][1][0] <= n && dp[2 * n][1][1] <= n)) { retrieve(2 * n, 1, n); reverse(ans.begin(), ans.end()); cout << ans; } else { cout << -1; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...