제출 #376816

#제출 시각아이디문제언어결과실행 시간메모리
376816VROOM_VARUN건물 4 (JOI20_building4)C++14
100 / 100
456 ms142324 KiB
/* ID: varunra2 LANG: C++ TASK: building4 */ #include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "lib/debug.h" #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define debug_arr(...) \ cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__) #pragma GCC diagnostic ignored "-Wsign-compare" //#pragma GCC diagnostic ignored "-Wunused-parameter" //#pragma GCC diagnostic ignored "-Wunused-variable" #else #define debug(...) 42 #endif #define EPS 1e-9 #define IN(A, B, C) assert(B <= A && A <= C) #define INF (int)1e9 #define MEM(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000007 #define MP make_pair #define PB push_back #define all(cont) cont.begin(), cont.end() #define rall(cont) cont.end(), cont.begin() #define x first #define y second const double PI = acos(-1.0); typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef map<int, int> MPII; typedef multiset<int> MSETI; typedef set<int> SETI; typedef set<string> SETS; typedef vector<int> VI; typedef vector<PII> VII; typedef vector<VI> VVI; typedef vector<string> VS; #define rep(i, a, b) for (int i = a; i < (b); ++i) #define trav(a, x) for (auto& a : x) #define sz(x) (int)(x).size() typedef pair<int, int> pii; typedef vector<int> vi; #pragma GCC diagnostic ignored "-Wsign-compare" // util functions int n; void solve(VVI& dpl, VVI& dpr, int i, int j, VI& ret, int cnt, VVI& vals) { ret[i] = j; if (j == 0) cnt++; if (i == 0) return; if (dpl[i - 1][0] <= (n - cnt) and dpr[i - 1][0] >= (n - cnt) and vals[0][i - 1] <= vals[j][i]) { solve(dpl, dpr, i - 1, 0, ret, cnt, vals); } else { solve(dpl, dpr, i - 1, 1, ret, cnt, vals); } } int main() { cin.sync_with_stdio(0); cin.tie(0); cin >> n; VVI vals(2, VI(2 * n)); trav(x, vals[0]) cin >> x; trav(x, vals[1]) cin >> x; VVI dpl(2 * n, VI(2, INF)); VVI dpr(2 * n, VI(2, -1)); dpl[0][0] = dpr[0][0] = 1; dpl[0][1] = dpr[0][1] = 0; for (int i = 1; i < 2 * n; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { if (dpl[i - 1][k] == INF) continue; if (vals[j][i] < vals[k][i - 1]) continue; // you can go from (i - 1, k) -> (i, j) dpl[i][j] = min(dpl[i][j], dpl[i - 1][k] + (j == 0 ? 1 : 0)); dpr[i][j] = max(dpr[i][j], dpr[i - 1][k] + (j == 0 ? 1 : 0)); } } } VI ret(2 * n, 0); if (dpl.back()[0] > n or dpr.back()[0] < n) { if (dpl.back()[1] > n or dpr.back()[1] < n) { cout << "-1\n"; return 0; } else { solve(dpl, dpr, 2 * n - 1, 1, ret, 0, vals); } } else { solve(dpl, dpr, 2 * n - 1, 0, ret, 0, vals); } for (int i = 0; i < 2 * n; i++) { if (ret[i] == 0) cout << 'A'; else cout << 'B'; } cout << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...