Submission #1145852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145852		SmuggingSpun	Building 4 (JOI20_building4)	C++20	11 / 100	18 ms	1476 KiB

building4

#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
int n;
namespace sub1{
	const int lim = 2e3 + 5;
	bitset<lim>dp[lim][2];
	void solve(){
		for(int i = 0; i < lim; i++){
			dp[i][0].reset();
			dp[i][1].reset();
		}
		vector<int>a(n << 1), b(n << 1);
		for(int& x : a){
			cin >> x;
		}
		for(int& x : b){
			cin >> x;
		}
		dp[1][0].set(0);
		dp[0][1].set(1);
		for(int i = 0; i <= n; i++){
			for(int j = 0; j <= n; j++){
				int sum = i + j;
				if(sum > 1){
					if(i > 0 && ((a[sum - 1] >= a[sum - 2] && dp[i - 1][0].test(j)) || (a[sum - 1] >= b[sum - 2] && dp[i - 1][1].test(j)))){
						dp[i][0].set(j);
					}
					if(j > 0 && ((b[sum - 1] >= a[sum - 2] && dp[i][0].test(j - 1)) || (b[sum - 1] >= b[sum - 2] && dp[i][1].test(j - 1)))){
						dp[i][1].set(j);
					}
				}
			}
		}
		if(!dp[n][0].test(n) && !dp[n][1].test(n)){
			return void(cout << -1);
		}
		vector<int>I(2, n);
		int j = int(dp[n][1].test(n));
		string ans = "";
		for(int _ = (n << 1) - 1; true; _--){
			ans += (j == 0 ? 'A' : 'B');
			if(_ == 0){
				break;
			}
			I[j]--;
			if(!dp[I[0]][j].test(I[1]) || (j == 0 && a[I[0] + I[1]] < a[I[0] + I[1] - 1]) || (j == 1 && b[I[0] + I[1]] < b[I[0] + I[1] - 1])){
				j ^= 1;
			}
		}
		reverse(ans.begin(), ans.end());
		cout << ans;
	}
}
namespace sub2{
	void solve(){
		
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n;
	if(n <= 2000){
		sub1::solve();
	}
	else{
		sub2::solve();
	}
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:63:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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