제출 #1145863

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1145863		SmuggingSpun	건물 4 (JOI20_building4)	C++20	100 / 100	133 ms	26024 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{
	const int lim = 1e6 + 5;
	pair<int, int>dp[lim][2];
	pair<int, int>merge(pair<int, int>a, pair<int, int>b){
		return make_pair(min(a.first, b.first), max(a.second, b.second));
	}
	bool inside(int i, pair<int, int>range){
		return range.first <= i && range.second >= i;
	}
	void solve(){
		vector<int>a(n << 1), b(n << 1);
		for(int& x : a){
			cin >> x;
		}
		for(int& x : b){
			cin >> x;
		}
		dp[0][0] = make_pair(0, 0);
		dp[0][1] = make_pair(1, 1);
		for(int i = 1; i < (n << 1); i++){
			dp[i][0] = dp[i][1] = make_pair(-1, -1);
			if(a[i] >= a[i - 1] && dp[i - 1][0].first != -1){
				dp[i][0] = dp[i - 1][0];
			}
			if(a[i] >= b[i - 1] && dp[i - 1][1].first != -1){
				dp[i][0] = (dp[i][0].first == -1 ? dp[i - 1][1] : merge(dp[i][0], dp[i - 1][1]));
			}
			if(b[i] >= a[i - 1] && dp[i - 1][0].first != -1){
				dp[i][1] = make_pair(dp[i - 1][0].first + 1, dp[i - 1][0].second + 1);
			}
			if(b[i] >= b[i - 1] && dp[i - 1][1].first != -1){
				pair<int, int>nxt = make_pair(dp[i - 1][1].first + 1, dp[i - 1][1].second + 1);
				dp[i][1] = (dp[i][1].first == -1 ? nxt : merge(dp[i][1], nxt));
			}
		}
		int I = (inside(n, dp[(n << 1) - 1][0]) ? 0 : (inside(n, dp[(n << 1) - 1][1]) ? 1 : -1));
		if(I == -1){
			return void(cout << -1);
		}
		string ans = "";
		for(int i = (n << 1) - 1; true; i--){
			ans += (I == 0 ? 'A' : 'B');
			if(i == 0){
				break;
			}
			if(I == 0){
				if(a[i] < a[i - 1] || !inside(n, dp[i - 1][0])){
					I = 1;
				}				
			}
			else if(!inside(--n, dp[i - 1][1]) || b[i] < b[i - 1]){
				I = 0;
			}
		}
		reverse(ans.begin(), ans.end());
		cout << ans;
	}
}
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();
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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

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