제출 #261612

#제출 시각아이디문제언어결과실행 시간메모리
261612KCSC건물 4 (JOI20_building4)C++14
100 / 100
1276 ms45340 KiB
#include <iostream> #include <algorithm> #include <vector> using namespace std; const int DIM = 1000005; pair<int, int> seg[2][DIM]; char ans[DIM]; int arr[2][DIM]; void solve(int k, int n, int rem) { if (n == 0) cout << (ans + 1); else { if (k == 0) ans[n] = 'A'; else ans[n] = 'B'; if (arr[0][n - 1] <= arr[k][n] and seg[0][n - 1].first != -1 and seg[0][n - 1].first <= rem - (1 - k) and rem - (1 - k) <= seg[0][n - 1].second) solve(0, n - 1, rem - (1 - k)); else solve(1, n - 1, rem - (1 - k)); } } void update(pair<int, int> &s1, pair<int, int> &s2) { if (s2.first == -1) return; if (s1.first == -1) s1 = s2; else s1 = make_pair(min(s1.first, s2.first), max(s1.second, s2.second)); } int main(void) { // freopen("building4.in", "r", stdin); // freopen("building4.out", "w", stdout); int n; cin >> n; for (int k = 0; k <= 1; ++k) { for (int i = 1; i <= n * 2; ++i) { cin >> arr[k][i]; seg[k][i] = {-1, -1}; } } seg[0][0] = {0, 0}; for (int i = 1; i <= n * 2; ++i) { for (int k1 = 0; k1 <= 1; ++k1) for (int k2 = 0; k2 <= 1; ++k2) if (arr[k1][i - 1] <= arr[k2][i]) update(seg[k2][i], seg[k1][i - 1]); if (seg[0][i].first != -1) ++seg[0][i].first, ++seg[0][i].second; } /* for (int i = 0; i <= n * 2; ++i) { for (int k = 0; k <= 1; ++k) cout << seg[k][i].first << " " << seg[k][i].second << " "; cout << endl; } */ if (seg[0][n * 2].first != -1 and seg[0][n * 2].first <= n and seg[0][n * 2].second >= n) solve(0, n * 2, n); else if (seg[1][n * 2].first != -1 and seg[1][n * 2].first <= n and seg[1][n * 2].second >= n) solve(1, n * 2, n); else cout << -1 << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...