Submission #218765

#	Time	Username	Problem	Language	Result	Execution time	Memory
218765		tincamatei	Building 4 (JOI20_building4)	C++14	0 / 100	7 ms	384 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;
		}
	}

	for(int startJ = 0; startJ < 3; ++startJ) {
		std::string rez;
		bool ok = true;
		int j = 0, cntA = 0, cntB = 0;
		for(int i = 0; i < N; ++i) {
			if(ok && path[i][j] == -1) {
				ok = false;
			} else if(ok) {
				rez.push_back(newChr[path[i][j]]);
				cntA += (path[i][j] == 0);
				cntB += (path[i][j] == 1);
			}
			j = path[i][j];
		}
		if(ok) {
			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(ok && cntA == N / 2 && cntB == N / 2) {
			printf("%s", rez.c_str());
			return 0;
		}
	}

	printf("-1");
	return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:67:21: 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