제출 #824836

#제출 시각아이디문제언어결과실행 시간메모리
824836xink건물 4 (JOI20_building4)C++14
11 / 100
2084 ms32700 KiB
#include <iostream> #include <vector> #include <utility> #include <sstream> #include <climits> #include <cstring> #include <algorithm> #define ll long long #define ld long double using namespace std; const ll mod = 1e9 + 7; const int maxn = 5e5 + 5, maxn1 = 2e3 + 5; typedef vector<int> vi; typedef pair<int, int> ii; typedef vector<ii> vii; bool can_construct[maxn1][maxn1][2]; int a[2 * maxn], b[2 * maxn]; void solve() { int n; cin >> n; for (int i = 0; i < 2 * n; i++) { cin >> a[i]; } for (int i = 0; i < 2 * n; i++) { cin >> b[i]; } can_construct[1][0][0] = can_construct[0][1][1] = 1; for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { if (i + j < 2) continue; if (i > 1) can_construct[i][j][0] |= can_construct[i - 1][j][0] && a[i + j - 1] >= a[i + j - 2]; if (j > 1) can_construct[i][j][1] |= can_construct[i][j - 1][1] && b[i + j - 1] >= b[i + j - 2]; if (i != 0 && j != 0) { can_construct[i][j][0] |= can_construct[i - 1][j][1] && a[i + j - 1] >= b[i + j - 2]; can_construct[i][j][1] |= can_construct[i][j - 1][0] && b[i + j - 1] >= a[i + j - 2]; } } } if (!can_construct[n][n][0] && !can_construct[n][n][1]) { cout << "-1"; return; } string ans; int i = n, j = n, last_pos = (can_construct[n][n][0] ? 0 : 1); while (i || j) { if (i == 0 && j == 1) { ans.push_back('B'); break; } if (j == 0 && i == 1) { ans.push_back('A'); break; } if (last_pos == 0) { ans.push_back('A'); if (i > 1 && can_construct[i - 1][j][0] && a[i + j - 1] >= a[i + j - 2]) last_pos = 0; else if (i > 0 && j > 0 && can_construct[i - 1][j][1] && a[i + j - 1] >= b[i + j - 2]) last_pos = 1; i--; } else { ans.push_back('B'); if (j > 1 && can_construct[i][j - 1][1] && b[i + j - 1] >= b[i + j - 2]) last_pos = 1; else if (i > 0 && j > 0 && can_construct[i][j - 1][0] && b[i + j - 1] >= a[i + j - 2]) last_pos = 0; j--; } } reverse(ans.begin(), ans.end()); cout << ans; } int main() { // freopen("input_text", "r", stdin); // freopen("output_text", "w", stdout); // ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while (t-- > 0) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...