Submission #709555

#TimeUsernameProblemLanguageResultExecution timeMemory
709555RandomLBBuilding 4 (JOI20_building4)C++17
0 / 100
1 ms468 KiB
#include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; #define all(x) x.begin(), x.end() #define ms(x, a) memset(x, a, sizeof(x)) #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values){ cout << vars << " = "; string delim = ""; (...,(cout << delim << values, delim = ", ")); cout << endl; } //=========================================== const int MAX = 1e6+5; int a[MAX], b[MAX], dp[2][2][MAX]; int main(){ cin.tie(0)->sync_with_stdio(0); int n; cin >> n; n*=2; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) cin >> b[i]; for (int i = 1; i <= n; i++){ dp[0][0][i] = dp[1][0][i] = INF; if (a[i] >= a[i-1]){ dp[0][0][i] = min(dp[0][0][i], dp[0][0][i-1]+1); dp[0][1][i] = max(dp[0][1][i], dp[0][1][i-1]+1); } if (a[i] >= b[i-1]){ dp[0][0][i] = min(dp[0][0][i], dp[1][0][i-1]+1); dp[0][1][i] = max(dp[0][1][i], dp[1][1][i-1]+1); } if (b[i] >= a[i-1]){ dp[1][0][i] = min(dp[1][0][i], dp[0][0][i-1]); dp[1][1][i] = max(dp[1][1][i], dp[0][1][i-1]); } if (b[i] >= b[i-1]){ dp[1][0][i] = min(dp[1][0][i], dp[1][0][i-1]); dp[1][1][i] = max(dp[1][1][i], dp[1][1][i-1]); } } //deb(dp[0][0][n], dp[1][0][n], dp[0][1][n], dp[1][1][n]); if ((dp[0][0][n] <= n/2 && n/2 <= dp[0][1][n]) || (dp[1][0][n] <= n/2 && n/2 <= dp[1][1][n])){ string res = ""; int c = (dp[1][0][n] <= n/2 && n/2 <= dp[1][1][n]); int rem = n/2; for (int i = n; i; i--){ res += (c? 'B' : 'A'); rem -= (!c); c = (dp[1][0][i-1] <= rem && rem <= dp[1][1][i-1]); } reverse(all(res)); cout << res << "\n"; return 0; } cout << -1 << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...