oj.uz

답안 #218760

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
218760 2020-04-02T17:19:55 Z tincamatei 건물 4 (JOI20_building4) C++14
0 / 100
 7 ms 512 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Incorrect 7 ms 512 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 89.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Incorrect 7 ms 512 KB Output isn't correct
10 Halted 0 ms 0 KB -