Submission #211617

#	Time	Username	Problem	Language	Result	Execution time	Memory
211617		khsoo01	Building 4 (JOI20_building4)	C++11	100 / 100	428 ms	29028 KiB

building4

#include<bits/stdc++.h>
using namespace std;

const int N = 1000005, inf = 2e9;
int n, a[N][2], s[N][2], e[N][2];

int main()
{
	scanf("%d",&n);
	n *= 2;
	for(int j=0;j<2;j++) {
		for(int i=1;i<=n;i++) {
			scanf("%d",&a[i][j]);
		}
	}
	for(int i=1;i<=n;i++) {
		for(int j=0;j<2;j++) {
			s[i][j] = inf, e[i][j] = -inf;
			for(int k=0;k<2;k++) {
				if(e[i-1][k] < 0 || a[i-1][k] > a[i][j]) continue;
				s[i][j] = min(s[i][j], s[i-1][k] + (j==0));
				e[i][j] = max(e[i][j], e[i-1][k] + (j==0));
			}
		}
	}
	vector<int> ans;
	if(s[n][0] <= n/2 && n/2 <= e[n][0]) ans.push_back(0);
	else if(s[n][1] <= n/2 && n/2 <= e[n][1]) ans.push_back(1);
	else {puts("-1"); return 0;}
	int L = n/2;
	for(int i=n;i>1;i--) {
		int j = ans.back();
		if(j == 0) L--;
		for(int k=0;k<2;k++) {
			if(e[i-1][k] < 0 || a[i-1][k] > a[i][j]) continue;
			if(s[i-1][k] <= L && L <= e[i-1][k]) {
				ans.push_back(k);
				break;
			}
		}
	}
	for(int i=n;i--;) {
		putchar('A' + ans[i]);
	}
	puts("");
}

Compilation message (stderr)

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);
  ~~~~~^~~~~~~~~
building4.cpp:13:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~

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