Submission #252027

#	Time	Username	Problem	Language	Result	Execution time	Memory
252027		Bruteforceman	Building 4 (JOI20_building4)	C++11	100 / 100	422 ms	38288 KiB

building4

#include "bits/stdc++.h"
using namespace std;
int a[2][500010 * 2];
int main(int argc, char const *argv[])
{
	int n;
	scanf("%d", &n);
	for(int x = 0; x < 2; x++) {
		for(int i = 0; i < 2*n; i++) {
			scanf("%d", &a[x][i]);	
		}
	}
	vector <int> v;
	if(a[0][0] <= a[1][0]) {
		v.push_back(0);
	} else {
		v.push_back(1);
	}
	for(int i = 0; i < 2*n - 1; i++) {
		int opt = -1;
		for(int x = 0; x < 2; x++) {
			if(a[v.back()][i] <= a[x][i + 1]) {
				if(opt == -1 || a[x][i + 1] < a[opt][i + 1]) {
					opt = x;
				}
			}
		}
		if(opt == -1) {
			puts("-1");
			exit(0);
		}
		v.push_back(opt);
	}
	vector <int> p (2*n + 1);
	vector <int> nxt (2*n + 1);
	p[2*n] = 0;
	for(int i = 2*n-1; i >= 0; i--) {
		p[i] = p[i + 1] + ((v[i] == 0) ? -1 : 1);
		if(i == 2*n - 1 || a[v[i] ^ 1][i] <= a[v[i + 1]][i + 1]) {
			nxt[i] = i;
		} else {
			if(a[v[i] ^ 1][i] <= a[v[i + 1] ^ 1][i + 1]) nxt[i] = nxt[i + 1];
			else nxt[i] = -1;
		}
		if(a[v[i]][i] > a[v[i] ^ 1][i]) {
			nxt[i] = -1;
		}
	}
	int sum = p[0];
	int last = 2*n;
	for(int i = 2*n - 1; i >= 0; i--) {
		if(nxt[i] == -1) continue;
		int c = min(nxt[i] + 1, last);
		int profit = p[c] - p[i];
		if(abs(sum + 2*profit) < abs(sum)) {
			sum += 2*profit;
			for(int j = i; j < c; j++) {
				v[j] ^= 1;
			}
			last = i; 
		}
	}
	if(sum == 0) {
		for(int i = 0; i < 2*n; i++) printf("%c", v[i] + 'A');
		printf("\n");
	} else printf("-1\n");
	return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int main(int, const char**)':
building4.cpp:7:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
building4.cpp:10:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a[x][i]); 
    ~~~~~^~~~~~~~~~~~~~~~

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