Submission #810305

#TimeUsernameProblemLanguageResultExecution timeMemory
810305ZHIRDILBILDIZBuilding 4 (JOI20_building4)C++14
0 / 100
26 ms49876 KiB
#include<bits/stdc++.h> #define fi first #define se second #define ll long long using namespace std ; const int N = 5e5 ; int n, a[2 * N + 1], b[2 * N + 1], dp[4 * N + 1] ; vector<char> ans ; bool pz[4 * N + 1], us[4 * N + 1] ; vector<int> v[4 * N + 1] ; void dfs(int city) { bool fl = 0 ; int mx = 0 ; us[city] = 1 ; for(int i : v[city]) { if(us[i]) { if(pz[i]) { fl = 1 ; mx = max(mx, dp[i]) ; } continue ; } dfs(i) ; if(pz[i]) { fl = 1 ; mx = max(mx, dp[i]) ; } } if(fl || city % n == 0) { pz[city] = 1 ; dp[city] = mx + (city > n) ; } } void get_ans(int city, int now) { // cout<<city << ' ' << now << '\n' ; if(city <= n) ans.push_back('A') ; else ans.push_back('B') ; us[city] = 1 ; if(city % n == 0) { for(char i : ans) cout << i ; exit(0) ; } for(int i : v[city]) { if(us[i] || now + dp[i] < n / 2) continue ; get_ans(i, now + (i > n)) ; // cout << city << '\n' ; } ans.pop_back() ; } void ultra_clear() { for(int i = 1 ; i <= 4 * N ; i++) us[i] &= 0 ; } signed main() { ios_base::sync_with_stdio( 0 ) ; cin.tie( 0 ) ; cout.tie( 0 ) ; cin >> n ; n *= 2 ; for(int i = 1 ; i <= n ; i++) cin >> a[i] ; for(int i = 1 ; i <= n ; i++) cin >> b[i] ; // if(n <= 4000) // { // bool gr[n + 1][n + 1][2] = {} ; // gr[1][0][0] = 1 ; // gr[1][1][1] = 1 ; // gr[0][0][0] = 1 ; // for(int i = 2 ; i <= n ; i++) // for(int j = 0 ; j <= n ; j++) // { // if(a[i] >= a[i - 1]) // gr[i][j][0] |= gr[i - 1][j][0] ; // if(a[i] >= b[i - 1]) // gr[i][j][0] |= gr[i - 1][j][1] ; // if(j) // { // if(b[i] >= a[i - 1]) // gr[i][j][1] |= gr[i - 1][j - 1][0] ; // if(b[i] >= b[i - 1]) // gr[i][j][1] |= gr[i - 1][j - 1][1] ; // } // } // if(gr[n][n / 2][0] || gr[n][n / 2][1]) // { // pair<pair<int, int>, bool> last = {{n, n / 2}, 0} ; // if(gr[n][n / 2][1])last.se = 1 ; // for(int i = n - 1 ; i >= 0 ; i--) // if(!last.se) // { // ans.push_back('A') ; // if(a[i] <= a[i + 1] && gr[i][last.fi.se][0]) // { // last = {{i, last.fi.se}, 0} ; // continue ; // } // if(b[i] <= a[i + 1] && gr[i][last.fi.se][1]) // { // last = {{i, last.fi.se}, 1} ; // continue ; // } // } // else // { // if(!last.fi.se) // continue ; // ans.push_back('B') ; // if(a[i] <= b[i + 1] && gr[i][last.fi.se - 1][0]) // { // last = {{i, last.fi.se - 1}, 0} ; // continue ; // } // if(b[i] <= b[i + 1] && gr[i][last.fi.se - 1][1]) // { // last = {{i, last.fi.se - 1}, 1} ; // continue ; // } // } // reverse(ans.begin(), ans.end()) ; // for(char i : ans) // cout << i ; // } // else // cout << "-1\n" ; // return 0 ; // } ans.clear() ; for(int i = 1 ; i < n ; i++) { if(a[i] <= a[i + 1]) v[i].push_back(i + 1) ; if(a[i] <= b[i + 1]) v[i].push_back(n + i + 1) ; if(b[i] <= a[i + 1]) v[n + i].push_back(i + 1) ; if(b[i] <= b[i + 1]) v[n + i].push_back(n + i + 1) ; } dfs(1) ; dfs(n + 1) ; // for(int i = 1 ; i <= 2 * n ; i++) // { // cout << dp[i] << ' ' ; // if(i == n)cout << '\n' ; // } // cout << '\n' ; ultra_clear() ; get_ans(1, 0) ; // cout << "_______________________\n" ; ultra_clear() ; get_ans(n + 1, 1) ; // cout << "_______________________\n" ; cout << "-1\n" ; return 0 ; } //5 //1 2 4 8 6 1 9 2 7 2 //9 10 1 4 7 6 6 7 5 7 //3 //1 2 9 6 10 7 //5 8 8 9 5 10
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...