Submission #218760

#	Time	Username	Problem	Language	Result	Execution time	Memory
218760		tincamatei	Building 4 (JOI20_building4)	C++14	0 / 100	7 ms	512 KiB

building4

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500000 * 2;

int A[1+MAX_N], B[1+MAX_N];
int path[1+MAX_N][3];
char newChr[3+1] = "AB?";

int main() {
	int N;

	scanf("%d", &N);
	N = 2 * N;
	for(int i = 1; i <= N; ++i)
		scanf("%d", &A[i]);
	for(int i = 1; i <= N; ++i) {
		scanf("%d", &B[i]);
		path[i - 1][0] = path[i - 1][1] = path[i - 1][2] = -1;
	}

	for(int i = N; i > 0; --i) {
		if(path[i][0] != -1) {
			if(A[i - 1] <= A[i])
				path[i - 1][0] = 0;
			if(B[i - 1] <= A[i])
				path[i - 1][1] = 0;
			if(std::max(A[i - 1], B[i - 1]) <= A[i])
				path[i - 1][2] = 0;
		}

		if(path[i][1] != -1) {
			if(A[i - 1] <= B[i])
				path[i - 1][0] = 1;
			if(B[i - 1] <= B[i])
				path[i - 1][1] = 1;
			if(std::max(A[i - 1], B[i - 1]) <= B[i])
				path[i - 1][2] = 1;
		}
		
		if(path[i][2] != -1) {
			if(A[i - 1] <= std::min(A[i], B[i]))
				path[i - 1][0] = 2;
			if(B[i - 1] <= std::min(A[i], B[i]))
				path[i - 1][1] = 2;
			if(std::max(A[i - 1], B[i - 1]) <= std::min(A[i], B[i]))
				path[i - 1][2] = 2;
		}
	}
	
	std::string rez;
	int j = 0, cntA = 0, cntB = 0;
	for(int i = 0; i < N; ++i) {
		if(path[i][j] == -1) {
			printf("-1");
			return 0;
		} else {
			rez.push_back(newChr[path[i][j]]);
			cntA += (path[i][j] == 0);
			cntB += (path[i][j] == 1);
		}
		j = path[i][j];
	}

	for(int i = 0; i < rez.size(); ++i)
		if(rez[i] == '?' && cntA < N / 2) {
			rez[i] = 'A';
			++cntA;
		} else if(rez[i] == '?' && cntB < N / 2) {
			rez[i] = 'B';
			++cntB;
		}

	if(cntA == N / 2 && cntB == N / 2)
		printf("%s", rez.c_str());
	else
		printf("-1");
	return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < rez.size(); ++i)
                 ~~^~~~~~~~~~~~
building4.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
building4.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &A[i]);
   ~~~~~^~~~~~~~~~~~~
building4.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &B[i]);
   ~~~~~^~~~~~~~~~~~~

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