Submission #261904

#TimeUsernameProblemLanguageResultExecution timeMemory
261904rulerBuilding 4 (JOI20_building4)C++14
100 / 100
395 ms27768 KiB
// IOI 2021 #include <bits/stdc++.h> using namespace std; #define endl '\n' #define ends ' ' #define endt '\t' #define die(x) return cout << x << endl, 0 #define all(v) v.begin(), v.end() #define sz(x) (int)(x.size()) void debug_out() { cerr << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); } #define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__) typedef long long ll; typedef pair<int, int> pii; const int INF = 1e9; const ll MOD = 1e9 + 7; //////////////////////////////////////////////////////////////////// const int N = 1e6 + 5; int DP[N][2][2]; int A[2][N]; bool R[N]; int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); mt19937 Rnd(time(0)); for (int i = 0; i < N; i++) for (int j = 0; j < 2; j++) DP[i][j][0] = INF, DP[i][j][1] = - INF; int n; cin >> n; for (int i = 0; i < 2; i++) for (int j = 0; j < n + n; j++) cin >> A[i][j]; DP[0][1][0] = DP[0][1][1] = 1; DP[0][0][0] = DP[0][0][1] = 0; for (int i = 1; i < n + n; i++) for (int j = 0; j < 2; j++) { if (A[j][i - 1] <= A[j][i]) { DP[i][j][0] = min(DP[i][j][0], DP[i - 1][j][0] + j); DP[i][j][1] = max(DP[i][j][1], DP[i - 1][j][1] + j); } if (A[1 - j][i - 1] <= A[j][i]) { DP[i][j][0] = min(DP[i][j][0], DP[i - 1][1 - j][0] + j); DP[i][j][1] = max(DP[i][j][1], DP[i - 1][1 - j][1] + j); } } int cnt = n; for (int i = n + n - 1; i >= 0; i--) { bool ok = false; for (int j = 0; j < 2; j++) { if (i + 1 < n + n && A[j][i] > A[R[i + 1]][i + 1]) continue; if (DP[i][j][0] <= cnt && cnt <= DP[i][j][1]) { R[i] = j; ok = true; cnt -= j; break; } } if (!ok) die(-1); } for (int i = 0; i < n + n; i++) cout << (R[i] ? 'B' : 'A'); cout << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...