Submission #1227764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227764		ansori	Building 4 (JOI20_building4)	C++20	100 / 100	153 ms	33868 KiB

building4

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("my solution")
//#define int long long
#define ll long long
#define nlp nullptr
#define btc __builtin_popcount
#define sht int_fast16_t
#define ld double
#define fi first
#define se second
using namespace std;
const int N = 2e5 + 5 , K = 8 , B = 369;
const int md = 1e9 + 7;
const int inf = 1e9;
const long double eps = 1e-8;
const bool stres = 0;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void f(pair<int , int> &a , pair<int , int> b){
	a.fi = min(a.fi , b.fi);
	a.se = max(a.se , b.se);
}
void solve(){
	int n;
	cin >> n;
	n *= 2;
	int a[n + 2] , b[n + 2];
	for(int i = 1;i <= n; ++ i) cin >> a[i];
	for(int i = 1;i <= n; ++ i) cin >> b[i];
	pair<int , int> mp[n + 2][3];
	mp[1][0] = {1 , 1};
	mp[1][1] = {0 , 0};
	for(int i = 2;i <= n; ++ i){
		mp[i][0] = mp[i][1] = {inf , -inf};
		if(mp[i - 1][0].fi < inf){
			if(a[i] >= a[i - 1]) f(mp[i][0] , mp[i - 1][0]);
			if(b[i] >= a[i - 1]) f(mp[i][1] , mp[i - 1][0]);
		}
		if(mp[i - 1][1].fi < inf){
			if(a[i] >= b[i - 1]) f(mp[i][0] , mp[i - 1][1]);
			if(b[i] >= b[i - 1]) f(mp[i][1] , mp[i - 1][1]);
		}
		if(mp[i][0].fi < inf){
			mp[i][0].fi ++ , mp[i][0].se ++;
		}
		// cout << mp[i][0].fi << ' ' << mp[i][0].se << ' ' << mp[i][1].fi << ' ' << mp[i][1].se << '\n';
	}
	if((mp[n][0].fi > n / 2 or mp[n][0].se < n / 2) and (mp[n][1].fi > n / 2 or mp[n][1].se < n / 2)){
		cout << -1;
		return ;
	}
	string ans = "";
	int cnt = n / 2;
	if(mp[n][0].fi <= n / 2 and mp[n][0].se >= n / 2){
		ans += 'A';
		cnt --;
	}
	else ans += 'B';
	for(int i = n - 1; i >= 1; -- i){
		char l = ans.back();
		if(mp[i][0].fi <= cnt and mp[i][0].se >= cnt and a[i] <= a[i + 1] * (l == 'A') + b[i + 1] * (l != 'A')){
			cnt --;
			ans += 'A';
		}
		else{
			ans += 'B';
		}
	}
	reverse(ans.begin() , ans.end());
	cout << ans;
}
main()
{
	//freopen("seating.in", "r", stdin) , freopen("seating.out" , "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T --)
    {
    	solve();
    	cout << '\n';
    }
}
/*
test
*/

Compilation message (stderr)

building4.cpp:3:35: warning: bad option '-fmy solution' to pragma 'optimize' [-Wpragmas]
    3 | #pragma GCC optimize("my solution")
      |                                   ^
building4.cpp:19:46: warning: bad option '-fmy solution' to attribute 'optimize' [-Wattributes]
   19 | void f(pair<int , int> &a , pair<int , int> b){
      |                                              ^
building4.cpp:23:12: warning: bad option '-fmy solution' to attribute 'optimize' [-Wattributes]
   23 | void solve(){
      |            ^
building4.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main()
      | ^~~~
building4.cpp:72:6: warning: bad option '-fmy solution' to attribute 'optimize' [-Wattributes]
   72 | main()
      |      ^

• Subtask 1: 11 / 11
• Subtask 2: 89 / 89