제출 #868792

#제출 시각아이디문제언어결과실행 시간메모리
868792awu건물 4 (JOI20_building4)C++14
100 / 100
205 ms68884 KiB
#include <bits/extc++.h> using namespace __gnu_pbds; using namespace std; #define int long long #define ll long long // #define double long double #define all(x) x.begin(), x.end() #define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0) #define f first #define s second using pii = pair<int, int>; // #define endl '\n' const ll inf = 1ll << 60; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; n *= 2; vector<int> a(n), b(n); for(int i = 0; i < n; i++) { cin >> a[i]; } for(int i = 0; i < n; i++) { cin >> b[i]; } vector<pair<pii, pii>> dp(n, {{-1, -1}, {-1, -1}}); dp[n - 1] = {{1, 1}, {0, 0}}; auto merge = [&](pii a, pii b) { if(min(a, b) == pii{-1, -1}) return max(a, b); return pii{min(a.f, b.f), max(a.s, b.s)}; }; for(int i = n - 2; i >= 0; i--) { if(a[i] <= a[i + 1]) { dp[i].f = merge(dp[i].f, dp[i + 1].f); } if(a[i] <= b[i + 1]) { dp[i].f = merge(dp[i].f, dp[i + 1].s); } if(dp[i].f != pii{-1, -1}) { dp[i].f.f++; dp[i].f.s++; } if(b[i] <= a[i + 1]) { dp[i].s = merge(dp[i].s, dp[i + 1].f); } if(b[i] <= b[i + 1]) { dp[i].s = merge(dp[i].s, dp[i + 1].s); } // cout << i << " " << dp[i].f.f << " " << dp[i].f.s << " " << dp[i].s.f << " " << dp[i].s.s << endl; } int rem = n / 2; int last = -1; string ans; auto die = [&]() { cout << -1 << endl; exit(0); }; for(int i = 0; i < n; i++) { if(last <= a[i] && dp[i].f.f <= rem && rem <= dp[i].f.s) { ans += "A"; last = a[i]; rem--; } else if(last <= b[i] && dp[i].s != pii{-1, -1}) { ans += "B"; last = b[i]; } else { die(); } } if(count(all(ans), 'A') != n / 2) die(); cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...