Submission #1213065

#TimeUsernameProblemLanguageResultExecution timeMemory
1213065siewjhBuilding 4 (JOI20_building4)C++20
100 / 100
505 ms28816 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1000005; int arr[MAXN][2], mna[MAXN][2], mxa[MAXN][2]; int main(){ int nums; cin >> nums; for (int j = 0; j <= 1; j++) for (int i = 1; i <= nums << 1; i++) cin >> arr[i][j]; for (int i = 1; i <= nums << 1; i++){ for (int j = 0; j <= 1; j++){ int mn = 2 * MAXN, mx = -MAXN; for (int k = 0; k <= 1; k++) if (arr[i][j] >= arr[i - 1][k]){ mn = min(mn, mna[i - 1][k]); mx = max(mx, mxa[i - 1][k]); } mn += j; mx += j; mna[i][j] = mn; mxa[i][j] = mx; } } int req = nums, curr = -1; vector<int> ans(nums << 1); for (int i = nums << 1; i >= 1; i--){ for (int j = 0; j <= 1; j++){ if (i != nums << 1 && arr[i][j] > arr[i + 1][curr]) continue; if (mna[i][j] <= req && mxa[i][j] >= req){ curr = j; break; } } if (curr == -1){ cout << -1; return 0; } req -= curr; ans[i - 1] = curr; } for (int x : ans) cout << (char)('A' + x); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...