oj.uz

답안 #768386

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
768386 2023-06-28T04:12:26 Z minhcool 건물 4 (JOI20_building4) C++17
100 / 100
 203 ms 64672 KB 
#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e6 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
mt19937 rng(1);
 
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}
 
int n, a[N], b[N];
 
int maxia[N][2], maxib[N][2];
 
#ifdef local
void process(){
	cin >> n;
	for(int i = 1; i <= 2 * n; i++) cin >> a[i];
	for(int i = 1; i <= 2 * n; i++) cin >> b[i];
	for(int i = 1; i <= 2 * n; i++) maxia[i][0] = maxia[i][1] = maxib[i][0] = maxib[i][1] = -oo;
	maxia[2 * n][0] = maxib[2 * n][1] = 1;
	maxia[2 * n][1] = maxib[2 * n][0] = 0;
	for(int i = 2 * n - 1; i >= 1; i--){
		for(int j = 0; j < 2; j++){
			for(int lst = 0; lst < 2; lst++){
				int temp1 = (!j ? a[i] : b[i]);
				int temp2 = (!lst ? a[i + 1] : b[i + 1]);
				if(temp1 > temp2) continue;
				maxia[i][j] = max(maxia[i][j], maxia[i + 1][lst] + (j == 0));
				maxib[i][j] = max(maxib[i][j], maxib[i + 1][lst] + (j == 1));
			}
		//	cout << i << " " << j << " " << maxia[i][j] << " " << maxib[i][j] << "\n";
		}
	}
	int temp = -1;
	if(maxia[1][0] >= n && maxib[1][0] >= n) temp = 0;
	if(maxia[1][1] >= n && maxib[1][1] >= n) temp = 1;
	if(temp < 0){
		cout << -1 << "\n";
		return;
	}
	string s;
	int aa = (temp == 0), bb = (temp == 1), lst = temp;
	if(temp == 0) s += "A";
	else s += "B";
	for(int i = 2; i <= 2 * n; i++){
		int tempo = (lst == 0 ? a[i - 1] : b[i - 1]);
		if(a[i] < tempo){
			bb++;
			lst = 1;
			s += "B";
		}
		else if(b[i] < tempo){
			aa++;
			lst = 0;
			s += "A";
		}
		else if((maxia[i][0] >= n - aa) && (maxib[i][0] >= n - bb)){
			aa++;
			lst = 0;
			s += "A";
		}
		else{
			bb++;
			lst = 1;
			s += "B";
		}
	}
	cout << s;
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
#endif

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 480 KB Output is correct
16 Correct 1 ms 516 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 1 ms 468 KB Output is correct

Subtask #2
89.0 / 89.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 480 KB Output is correct
16 Correct 1 ms 516 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Correct 192 ms 60240 KB Output is correct
35 Correct 181 ms 63732 KB Output is correct
36 Correct 175 ms 62628 KB Output is correct
37 Correct 183 ms 62432 KB Output is correct
38 Correct 180 ms 63960 KB Output is correct
39 Correct 191 ms 63220 KB Output is correct
40 Correct 184 ms 51668 KB Output is correct
41 Correct 167 ms 64672 KB Output is correct
42 Correct 184 ms 56508 KB Output is correct
43 Correct 203 ms 51864 KB Output is correct
44 Correct 200 ms 52000 KB Output is correct
45 Correct 201 ms 51952 KB Output is correct
46 Correct 181 ms 51908 KB Output is correct
47 Correct 191 ms 61336 KB Output is correct
48 Correct 178 ms 62616 KB Output is correct
49 Correct 180 ms 51852 KB Output is correct
50 Correct 198 ms 59372 KB Output is correct
51 Correct 198 ms 60060 KB Output is correct
52 Correct 149 ms 56972 KB Output is correct
53 Correct 144 ms 56904 KB Output is correct
54 Correct 118 ms 56900 KB Output is correct
55 Correct 123 ms 56672 KB Output is correct
56 Correct 184 ms 52028 KB Output is correct
57 Correct 161 ms 63568 KB Output is correct
58 Correct 177 ms 63828 KB Output is correct
59 Correct 153 ms 63940 KB Output is correct
60 Correct 158 ms 60488 KB Output is correct
61 Correct 163 ms 64364 KB Output is correct
62 Correct 163 ms 63472 KB Output is correct
63 Correct 162 ms 64324 KB Output is correct
64 Correct 151 ms 62108 KB Output is correct
65 Correct 159 ms 64384 KB Output is correct