Submission #1113925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113925		Dan4Life	Building 4 (JOI20_building4)	C++17	100 / 100	207 ms	48336 KiB

building4

#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e6+10;
int n, ans[N], a[2][N], dp[2][2][N];
// dp[i][j][k]: i= min/max As used, j = placed A/B here?, considering till kth index

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n; dp[0][0][0] = dp[1][0][0] = 1;
	for(int i = 0; i < 2*n; i++) cin >> a[0][i];
	for(int i = 0; i < 2*n; i++) cin >> a[1][i];
	
	for(int i = 1; i < 2*n; i++)
		dp[0][0][i]=dp[0][1][i]=2*n;
	for(int i = 1; i < 2*n; i++)
		for(int k : {0,1}) for(int j : {0,1})
			if(a[j][i-1] <= a[k][i])
				dp[0][k][i] = min(dp[0][k][i],dp[0][j][i-1]+!k),
				dp[1][k][i] = max(dp[1][k][i],dp[1][j][i-1]+!k);
	for(int k : {0,1}){
		if(dp[0][k][2*n-1]<=n and dp[1][k][2*n-1]>=n){
			ans[2*n-1] = k; int sum = n-!k, prv = a[k][2*n-1];
			for(int i = 2*n-2; i>=0; i--){
				int cur = (!sum or dp[0][0][i]>sum or dp[1][0][i]<sum or dp[0][0][i]>dp[1][0][i] or prv<a[0][i]);
				ans[i]=cur; sum-=!cur; prv = a[cur][i];
			}
			for(int i = 0; i < 2*n; i++) 
				cout << "AB"[ans[i]]; cout << "\n";
			return 0;
		}
	}
	cout << -1 << "\n";
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:27:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   27 |    for(int i = 0; i < 2*n; i++)
      |    ^~~
building4.cpp:28:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   28 |     cout << "AB"[ans[i]]; cout << "\n";
      |                           ^~~~

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