제출 #894711

#제출 시각아이디문제언어결과실행 시간메모리
894711beaboss건물 4 (JOI20_building4)C++14
0 / 100
8 ms17240 KiB
// Source: https://oj.uz/problem/view/JOI20_building4 // #include "bits/stdc++.h" using namespace std; #define s second #define f first #define pb push_back typedef long long ll; typedef pair<int, int> pii; typedef vector<pii> vpii; typedef vector<int> vi; #define FOR(i, a, b) for (int i = (a); i<b; i++) bool ckmin(int& a, int b){ return b < a ? a = b, true : false; } bool ckmax(int& a, int b){ return b > a ? a = b, true : false; } const int N = (5e5 + 10) * 2; int a[N]; int b[N]; int c[N]; int oc[N]; int swaps[N]; // -1 if not possible, 1 if dependent, 2 if independent int cnt = 0; bool flipped=false; int n; char rev(char ff) { if (ff == 'A') { cnt--; return 'B'; } else { cnt++; return 'A'; } } string chk(string s) { if (flipped) { FOR(i, 0, n) s[i] = rev(s[i]); } int prv = -1; FOR(i, 0, n) { if (s[i] == 'A') { assert(a[i] >= prv); prv = a[i]; } else { assert(b[i] >= prv); prv = b[i]; } } return s; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; n *= 2; FOR(i, 0, n) { cin >> a[i]; } FOR(i, 0, n) cin >> b[i]; string ans; c[0] = min(a[0], b[0]); oc[0] = max(a[0], b[0]); if (c[0] == a[0]) { cnt++; ans += 'A'; } else ans += 'B'; for (int i = 1; i < n; i++) { if (min(a[i], b[i]) >= c[i-1]) { c[i] = min(a[i], b[i]); oc[i] = max(a[i], b[i]); } else if (max(a[i], b[i]) >= c[i-1]) { swaps[i]=-1; c[i] = max(a[i], b[i]); oc[i] = min(a[i], b[i]); } else { cout << -1 << endl; return 0; } if (c[i] == a[i]) { cnt++; ans += 'A'; } else ans += 'B'; } if (cnt == n/2) { cout << ans << endl; return 0; } if (cnt > n/2) { flipped=true; FOR(i, 0, n) ans[i] = rev(ans[i]); } c[n] = 1e9 + 10; for (int i = n-1; i >= 0; i--) { if (swaps[i] == -1) continue; assert(c[i] <= c[i+1]); if (oc[i] <= c[i + 1]) swaps[i]=2; // independent else if (swaps[i + 1] != -1 && oc[i] <= oc[i + 1]) swaps[i]=1; // dependent else swaps[i]=-1; } int st = n-1; int mx = -1; int pos; int res = 0; // assumes that A has less frequency for (int i = n-1; i >= 0; i--) { if (swaps[i] == -1 || swaps[i] == 2) { if (i != st) { if (mx == -1) continue; for (int j = st; j >= pos; j--) { if (cnt != n/2) ans[j] = rev(ans[j]); else { cout << chk(ans) << endl; return 0; } } } st = i-1; } if (swaps[i] == 2) { st = i; } if (swaps[i] != -1) { res -= (ans[i] == 'A'); res += (ans[i] == 'B'); if (res > mx) { pos = i; mx = res; } } // cout << i << st << mx << res << ans[i] << endl; } if (0 <= st) { for (int j = st; j >= 0; j--) { if (cnt != n/2) ans[j] = rev(ans[j]); else { cout << chk(ans) << endl; return 0; } } } if (cnt == n/2) cout << chk(ans) << endl; else cout << -1 << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...