Submission #651796

#	Time	Username	Problem	Language	Result	Execution time	Memory
651796		_HDH	Building 4 (JOI20_building4)	C++11	0 / 100	13 ms	31604 KiB

building4

#include <bits/stdc++.h>

#ifdef LOCAL
#include <debug.h>
#else
#define debug(...) 1001
#endif

using namespace std;
#define all(x) x.begin(), x.end()
#define st first
#define nd second
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define file "TEMPLATE"

typedef long long ll;
typedef pair<int, int> ii;
typedef array<int, 3> iii;
typedef vector<int> vi;
typedef vector<ll> vl;

bool const SINGLE_TEST = 1;

int const N = 2e3 + 1;

int n; 	
int arr[N][2];

bool is[N][N][2];
int dp[N][N][2];
bool p[N][N][2];

bool emrua(int i, int cnt, int last){
	if (cnt < 0) return 0;
	if (i == 2 * n + 1) return !cnt;
		
	if (dp[i][cnt][last] != -1) return dp[i][cnt][last];

	bool x = 0, y = 0;
	if (arr[i - 1][last] <= arr[i][0])
		x = emrua(i + 1, cnt - 1, 0);
	if (arr[i - 1][last] <= arr[i][1])
		y = emrua(i + 1, cnt    , 1);

	if (x) p[i][cnt][last] = 0;
	else p[i][cnt][last] = 1;
	return dp[i][cnt][last] = x | y;
}

void solve(){
	cin >> n;
	for (int i = 1; i <= 2 * n; i++) cin >> arr[i][0];
	for (int j = 1; j <= 2 * n; j++) cin >> arr[j][1];
		
	memset(dp, -1, sizeof dp);
		
	if (!emrua(1, n, 0)){
		cout << -1;
		return;
	}
	for (int i = 1, j = n, z = 0; i <= 2 * n; i++){
		if (!p[i][j][z]){
			cout << 'A'; j--, z = 0;
		}
		else {cout << 'B'; z = 1;}
	}
}

int main(){
	ios_base::sync_with_stdio(0);//      the
	cin.tie(0);cout.tie(0);// 	    magical lines	
	// freopen(file".inp", "r", stdin);
	// freopen(file".out", "w", stdout);
	int t;
	if (SINGLE_TEST) t = 1;
	else cin >> t;
	while (t--) solve();
	return 0;
}//it's coding time!

Compilation message (stderr)

building4.cpp: In function 'bool emrua(int, int, int)':
building4.cpp:53:26: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   53 |  return dp[i][cnt][last] = x | y;
      |         ~~~~~~~~~~~~~~~~~^~~~~~~

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