oj.uz

Submission #211603

# Submission time Handle Problem Language Result Execution time Memory
211603 2020-03-20T19:20:39 Z mieszko11b Building 4 (JOI20_building4) C++14
11 / 100
 433 ms 24184 KB 
#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

#define X first
#define Y second

int n;
ii dp[500007][2];
int a[500007], b[500007];

ii merge(ii a, ii b) {
	return {min(a.X, b.X), max(a.Y, b.Y)};
}

ii addone(ii a) {
	return {a.X + 1, a.Y + 1};
}

int main() {
	scanf("%d", &n);
	n *= 2;
	for(int i = 1 ; i <= n ; i++)
		scanf("%d", &a[i]);
	for(int i = 1 ; i <= n ; i++)
		scanf("%d", &b[i]);
		
	dp[1][0] = {1, 1};
	dp[1][1] = {0, 0};
	for(int i = 2 ; i <= n ; i++) {
		dp[i][0] = dp[i][1] = {1e9, -1e9};
		if(a[i] >= a[i - 1])
			dp[i][0] = merge(dp[i][0], addone(dp[i - 1][0]));
		if(a[i] >= b[i - 1])
			dp[i][0] = merge(dp[i][0], addone(dp[i - 1][1]));
		if(b[i] >= a[i - 1])
			dp[i][1] = merge(dp[i][1], dp[i - 1][0]);
		if(b[i] >= b[i - 1])
			dp[i][1] = merge(dp[i][1], dp[i - 1][1]);
	}
	
	string res;
	int ac = 1;
	if(!(dp[n][0].X <= n / 2 && n / 2 <= dp[n][0].Y)) ac = 2;
	if(!(dp[n][0].X <= n / 2 && n / 2 <= dp[n][0].Y) && !(dp[n][1].X <= n / 2 && n / 2 <= dp[n][1].Y)) {
		printf("-1\n");
		return 0;
	}
	
	//~ cout << dp[n - 1][0].X << " "<< dp[n - 1][0].Y << endl;
	
	res += (ac == 1 ? 'A' : 'B');
	int c = n / 2;
	for(int i = n ; i >= 2 ; i--) {
		//~ cout << n << " " << c << endl;
		
		int aac = 1;
		if(ac == 1)
			c--;
		if(!(dp[i - 1][0].X <= c && c <= dp[i - 1][0].Y && ((ac == 1 && a[i] >= a[i - 1]) || (ac == 2 && b[i] >= a[i - 1]))))
			aac = 2;

		ac = aac;
		res += (ac == 1 ? 'A' : 'B');
	}
		
	reverse(res.begin(), res.end());
	printf("%s\n", res.c_str());
		
	return 0;
}

Compilation message

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 7 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 10 ms 512 KB Output is correct
17 Correct 6 ms 512 KB Output is correct
18 Correct 6 ms 384 KB Output is correct
19 Correct 6 ms 384 KB Output is correct
20 Correct 6 ms 384 KB Output is correct
21 Correct 6 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 6 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 6 ms 384 KB Output is correct
27 Correct 7 ms 512 KB Output is correct
28 Correct 9 ms 384 KB Output is correct
29 Correct 8 ms 384 KB Output is correct
30 Correct 6 ms 512 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 5 ms 384 KB Output is correct
33 Correct 6 ms 384 KB Output is correct

Subtask #2
0 / 89.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 7 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 10 ms 512 KB Output is correct
17 Correct 6 ms 512 KB Output is correct
18 Correct 6 ms 384 KB Output is correct
19 Correct 6 ms 384 KB Output is correct
20 Correct 6 ms 384 KB Output is correct
21 Correct 6 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 6 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 6 ms 384 KB Output is correct
27 Correct 7 ms 512 KB Output is correct
28 Correct 9 ms 384 KB Output is correct
29 Correct 8 ms 384 KB Output is correct
30 Correct 6 ms 512 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 5 ms 384 KB Output is correct
33 Correct 6 ms 384 KB Output is correct
34 Runtime error 433 ms 24184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Halted 0 ms 0 KB -