Submission #651803

#	Time	Username	Problem	Language	Result	Execution time	Memory
651803		_HDH	Building 4 (JOI20_building4)	C++11	0 / 100	13 ms	31584 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];

int dp[N][N][2] = {};

bool emrua(int i, int cnt, int last){
	if (i == 2 * n + 1) return dp[i][cnt][last] = !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] && cnt)
		x = emrua(i + 1, cnt - 1, 0);
	if (arr[i - 1][last] <= arr[i][1])
		y = emrua(i + 1, cnt    , 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 (j && dp[i + 1][j - 1][0] == 1){
			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:38:46: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   38 |  if (i == 2 * n + 1) return dp[i][cnt][last] = !cnt;
      |                             ~~~~~~~~~~~~~~~~~^~~~~~
building4.cpp:48:26: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   48 |  return dp[i][cnt][last] = x | y;
      |         ~~~~~~~~~~~~~~~~~^~~~~~~
building4.cpp: In function 'void solve()':
building4.cpp:62:25: warning: variable 'z' set but not used [-Wunused-but-set-variable]
   62 |  for (int i = 1, j = n, z = 0; i <= 2 * n; i++){
      |                         ^

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