Submission #212516

#TimeUsernameProblemLanguageResultExecution timeMemory
212516combi1k1Building 4 (JOI20_building4)C++14
100 / 100
330 ms27500 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define ld double #define sz(x) (int)x.size() #define all(x) x.begin(),x.end() #define pb emplace_back #define X first #define Y second const int N = 1e6 + 5; typedef pair<int,int> ii; int a[N][2]; int l[N][2]; int r[N][2]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; n += n; for(int i = 1 ; i <= n ; ++i) cin >> a[i][0]; for(int i = 1 ; i <= n ; ++i) cin >> a[i][1]; for(int i = 1 ; i <= n ; ++i) { l[i][0] = l[i][1] = 1e9; r[i][0] = r[i][1] = -1e9; for(int x = 0 ; x < 2 ; ++x) for(int y = 0 ; y < 2 ; ++y) if (a[i - 1][x] <= a[i][y]) { l[i][y] = min(l[i][y],l[i - 1][x] + (y == 0)); r[i][y] = max(r[i][y],r[i - 1][x] + (y == 0)); } } int S = 0; int v = n / 2; if (l[n][0] > v) S = 1; if (r[n][0] < v) S = 1; if (l[n][S] > v) return cout << "-1",0; if (r[n][S] < v) return cout << "-1",0; string res = ""; for(int i = n ; i >= 1 ; --i) { if (S == 0) res += 'A', --v; if (S == 1) res += 'B'; for(int x = 0 ; x < 2 ; ++x) if (a[i - 1][x] <= a[i][S]) { if (l[i - 1][x] > v) continue; if (r[i - 1][x] < v) continue; S = x; break; } } reverse(all(res)); cout << res << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...