Submission #221465

#	Time	Username	Problem	Language	Result	Execution time	Memory
221465		patrikpavic2	Building 4 (JOI20_building4)	C++17	100 / 100	483 ms	48376 KiB

building4

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 500;

int L[N][2], R[N][2];
int A[N][2], ans[N], n;

void rekonstrukcija(int j){
	int cur = n;
	for(int i = 2 * n - 1;i >= 0;i--){
		ans[i] = j;
		cur -= j;
		//printf("cur = %d, i = %d\n", cur, i);
		if(A[i][j] >= A[i - 1][0] && L[i - 1][0] != -1 && L[i - 1][0] <= cur && R[i - 1][0] >= cur)
			j = 0;
		else
			j = 1;
	}
	for(int i = 0;i < 2 * n;i++)
		printf("%c", 'A' + ans[i]);
	printf("\n");
}

int main(){
	scanf("%d", &n);
	for(int j = 0;j < 2;j++)
		for(int i = 0;i < 2 * n;i++)
			scanf("%d", &A[i][j]);
	L[0][0] = 0, R[0][0] = 0;
	L[0][1] = 1, R[0][1] = 1;
	for(int i = 1;i < 2 * n;i++){
		for(int j = 0;j < 2;j++){
			L[i][j] = -1;
			if(A[i][j] >= A[i - 1][0] && L[i - 1][0] != -1){
				L[i][j] = L[i - 1][0];
				R[i][j] = R[i - 1][0];
			}
			if(A[i][j] >= A[i - 1][1] && L[i - 1][1] != -1){
				if(L[i][j] == -1){
					L[i][j] = L[i - 1][1];
					R[i][j] = R[i - 1][1];
				}
				else{
					L[i][j] = min(L[i - 1][1], L[i][j]);
					R[i][j] = max(R[i - 1][1], R[i][j]);
				}
			}
			if(L[i][j] != -1)
				L[i][j] += j, R[i][j] += j;
				//printf("%d, %d => [%d %d]\n", i, j, L[i][j], R[i][j]);
		}
	}
	if(L[2 * n - 1][0] != -1 && L[2 * n - 1][0] <= n && R[2 * n - 1][0] >= n)
		rekonstrukcija(0);
	else if(L[2 * n - 1][1] != -1 && L[2 * n - 1][1] <= n && R[2 * n - 1][1] >= n)
		rekonstrukcija(1);
	else
		printf("-1\n");
	return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
building4.cpp:32: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