Submission #212806

#	Time	Username	Problem	Language	Result	Execution time	Memory
212806		GioChkhaidze	Building 4 (JOI20_building4)	C++14	100 / 100	398 ms	36204 KiB

building4

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+6;
int n,a[N],b[N],dp[N][2][2];
main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	
	scanf("%d",&n); n*=2;
	for (int i=1; i<=n; i++)
		scanf("%d",&a[i]);
	for (int i=1; i<=n; i++)
		scanf("%d",&b[i]);
	
	for (int i=0; i<=n; i++) {
		dp[i][0][0]=1e9;
		dp[i][0][1]=-1e9;
		dp[i][1][0]=1e9;
		dp[i][1][1]=-1e9;
	}	

	dp[0][0][0]=0;
	dp[0][0][1]=0;
	dp[0][1][0]=0;
	dp[0][1][1]=0;
	
	for (int i=1; i<=n; i++) {
		if (a[i-1]<=a[i]) {
			dp[i][0][0]=min(dp[i][0][0],dp[i-1][0][0]+1);
			dp[i][0][1]=max(dp[i][0][1],dp[i-1][0][1]+1);
		}
		
		if (a[i-1]<=b[i]) {
			dp[i][1][0]=min(dp[i][1][0],dp[i-1][0][0]-1);
			dp[i][1][1]=max(dp[i][1][1],dp[i-1][0][1]-1);
		}
		
		if (b[i-1]<=a[i]) {
			dp[i][0][0]=min(dp[i][0][0],dp[i-1][1][0]+1);
			dp[i][0][1]=max(dp[i][0][1],dp[i-1][1][1]+1);
		}
		
		if (b[i-1]<=b[i]) {
			dp[i][1][0]=min(dp[i][1][0],dp[i-1][1][0]-1);
			dp[i][1][1]=max(dp[i][1][1],dp[i-1][1][1]-1);
		}
	}
	
	int f=0,l=1e9;
	string ans="";
	for (int i=n; i>=1; i--) {	
		if (dp[i][0][0]<=f && f<=dp[i][0][1] && a[i]<=l) {
			--f,l=a[i];
			ans+='A';
		}
			else
		if (dp[i][1][0]<=f && f<=dp[i][1][1] && b[i]<=l) {
			++f,l=b[i];
			ans+='B';
		}
			else {
			cout<<-1<<endl;
			return 0;
		}
	}
	
	reverse(ans.begin(),ans.end());
	cout<<ans<<endl;	
}

Compilation message (stderr)

building4.cpp:5:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
building4.cpp: In function 'int main()':
building4.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n); n*=2;
  ~~~~~^~~~~~~~~
building4.cpp:11:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~
building4.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&b[i]);
   ~~~~~^~~~~~~~~~~~

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