//
// Created by Ильдар Ялалов on 14.01.2020.
//
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf_int = 1e9 + 100;
const ll inf_ll = 1e18;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double dbl;
typedef unsigned int uint;
#define pb push_back
#define eb emplace_back
const double pi = 3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz(a) (int(a.size()))
#define mp make_pair
#define all(a) a.begin(),a.end()
#ifdef zxc
#include "debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
bool debug = 0;
const int MAXN = (1e6) + 100;
const int LOG = 21;
const int mod = 1e9 + 7;
const int MX = (1e7 + 100);
int a[MAXN], b[MAXN];
pii dp[MAXN][2];
pii operator+(pii &a, int b) {
if (a.fi < 0)
return a;
return {a.fi + b, a.se + b};
}
pii operator*(pii a, pii b) {
if (a.fi == -1)
return b;
if (b.fi == -1)
return a;
return {min(a.fi, b.fi), max(a.se, b.se)};
}
bool in(pii a, int x) {
return x >= a.fi && x <= a.se;
}
void solve() {
int n;
cin >> n;
for (int i = 1; i <= 2 * n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= 2 * n; ++i) {
cin >> b[i];
}
dp[0][0] = {0, 0};
dp[0][1] = {0, -1};
for (int i = 1; i <= 2 * n; ++i) {
dp[i][0] = dp[i][1] = {-1, -1};
if (a[i] >= a[i - 1]) {
dp[i][0] = dp[i - 1][0];
}
if (a[i] >= b[i - 1]) {
dp[i][0] = dp[i][0] * dp[i - 1][1];
}
dp[i][0] = dp[i][0] + 1;
if (b[i] >= a[i - 1]) {
dp[i][1] = dp[i - 1][0];
}
if (b[i] >= b[i - 1]) {
dp[i][1] = (dp[i][1] * dp[i - 1][1]);
}
debug(i, dp[i][0], dp[i][1]);
}
debug(dp[2 * n][0], dp[2 * n][1]);
int pos = -1;
if (in(dp[2 * n][0], n)) {
pos = 0;
} else if (in(dp[2 * n][1], n)) {
pos = 1;
} else {
cout << -1;
return;
}
int have = n;
string ans;
for (int i = 2 * n; i >= 1; --i) {
int val;
if (pos == 0) {
have--;
val = a[i];
ans.pb('A');
} else {
val = b[i];
ans.pb('B');
}
if (val >= a[i - 1] && in(dp[i - 1][0], have)) {
pos = 0;
} else {
pos = 1;
}
}
reverse(all(ans));
cout << ans << "\n";
return;
}
// CHECK LIMITS (n <= 10^5)
// CHECK CORNER CASES ( n==1)
signed main() {
#ifdef zxc
freopen("../input.txt", "r", stdin);
// freopen("../output.txt", "w", stdout);
#else
#endif //zxc
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout.setf(ios::fixed);
cout.precision(15);
int t = 1;
while (t--) {
solve();
}
debug(1.0 * clock() / CLOCKS_PER_SEC);
}
Compilation message
building4.cpp: In function 'void solve()':
building4.cpp:92:37: warning: statement has no effect [-Wunused-value]
debug(i, dp[i][0], dp[i][1]);
^
building4.cpp:94:38: warning: statement has no effect [-Wunused-value]
debug(dp[2 * n][0], dp[2 * n][1]);
^
building4.cpp: In function 'int main()':
building4.cpp:151:42: warning: statement has no effect [-Wunused-value]
debug(1.0 * clock() / CLOCKS_PER_SEC);
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
256 KB |
Output is correct |
3 |
Correct |
4 ms |
256 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
6 ms |
512 KB |
Output is correct |
6 |
Correct |
6 ms |
512 KB |
Output is correct |
7 |
Correct |
6 ms |
512 KB |
Output is correct |
8 |
Correct |
6 ms |
512 KB |
Output is correct |
9 |
Correct |
6 ms |
512 KB |
Output is correct |
10 |
Correct |
5 ms |
512 KB |
Output is correct |
11 |
Correct |
6 ms |
512 KB |
Output is correct |
12 |
Correct |
6 ms |
640 KB |
Output is correct |
13 |
Correct |
6 ms |
512 KB |
Output is correct |
14 |
Correct |
6 ms |
512 KB |
Output is correct |
15 |
Correct |
6 ms |
512 KB |
Output is correct |
16 |
Correct |
6 ms |
512 KB |
Output is correct |
17 |
Correct |
6 ms |
512 KB |
Output is correct |
18 |
Correct |
6 ms |
512 KB |
Output is correct |
19 |
Correct |
7 ms |
512 KB |
Output is correct |
20 |
Correct |
6 ms |
512 KB |
Output is correct |
21 |
Correct |
5 ms |
512 KB |
Output is correct |
22 |
Correct |
5 ms |
512 KB |
Output is correct |
23 |
Correct |
6 ms |
512 KB |
Output is correct |
24 |
Correct |
6 ms |
640 KB |
Output is correct |
25 |
Correct |
6 ms |
512 KB |
Output is correct |
26 |
Correct |
5 ms |
512 KB |
Output is correct |
27 |
Correct |
5 ms |
512 KB |
Output is correct |
28 |
Correct |
5 ms |
512 KB |
Output is correct |
29 |
Correct |
5 ms |
512 KB |
Output is correct |
30 |
Correct |
5 ms |
512 KB |
Output is correct |
31 |
Correct |
5 ms |
512 KB |
Output is correct |
32 |
Correct |
5 ms |
512 KB |
Output is correct |
33 |
Correct |
5 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
256 KB |
Output is correct |
3 |
Correct |
4 ms |
256 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
6 ms |
512 KB |
Output is correct |
6 |
Correct |
6 ms |
512 KB |
Output is correct |
7 |
Correct |
6 ms |
512 KB |
Output is correct |
8 |
Correct |
6 ms |
512 KB |
Output is correct |
9 |
Correct |
6 ms |
512 KB |
Output is correct |
10 |
Correct |
5 ms |
512 KB |
Output is correct |
11 |
Correct |
6 ms |
512 KB |
Output is correct |
12 |
Correct |
6 ms |
640 KB |
Output is correct |
13 |
Correct |
6 ms |
512 KB |
Output is correct |
14 |
Correct |
6 ms |
512 KB |
Output is correct |
15 |
Correct |
6 ms |
512 KB |
Output is correct |
16 |
Correct |
6 ms |
512 KB |
Output is correct |
17 |
Correct |
6 ms |
512 KB |
Output is correct |
18 |
Correct |
6 ms |
512 KB |
Output is correct |
19 |
Correct |
7 ms |
512 KB |
Output is correct |
20 |
Correct |
6 ms |
512 KB |
Output is correct |
21 |
Correct |
5 ms |
512 KB |
Output is correct |
22 |
Correct |
5 ms |
512 KB |
Output is correct |
23 |
Correct |
6 ms |
512 KB |
Output is correct |
24 |
Correct |
6 ms |
640 KB |
Output is correct |
25 |
Correct |
6 ms |
512 KB |
Output is correct |
26 |
Correct |
5 ms |
512 KB |
Output is correct |
27 |
Correct |
5 ms |
512 KB |
Output is correct |
28 |
Correct |
5 ms |
512 KB |
Output is correct |
29 |
Correct |
5 ms |
512 KB |
Output is correct |
30 |
Correct |
5 ms |
512 KB |
Output is correct |
31 |
Correct |
5 ms |
512 KB |
Output is correct |
32 |
Correct |
5 ms |
512 KB |
Output is correct |
33 |
Correct |
5 ms |
512 KB |
Output is correct |
34 |
Correct |
300 ms |
23544 KB |
Output is correct |
35 |
Correct |
292 ms |
24368 KB |
Output is correct |
36 |
Correct |
281 ms |
23728 KB |
Output is correct |
37 |
Correct |
282 ms |
24496 KB |
Output is correct |
38 |
Correct |
271 ms |
24724 KB |
Output is correct |
39 |
Correct |
266 ms |
24496 KB |
Output is correct |
40 |
Correct |
305 ms |
29164 KB |
Output is correct |
41 |
Correct |
272 ms |
24752 KB |
Output is correct |
42 |
Correct |
290 ms |
28464 KB |
Output is correct |
43 |
Correct |
311 ms |
29420 KB |
Output is correct |
44 |
Correct |
310 ms |
29420 KB |
Output is correct |
45 |
Correct |
307 ms |
29396 KB |
Output is correct |
46 |
Correct |
305 ms |
29420 KB |
Output is correct |
47 |
Correct |
305 ms |
29364 KB |
Output is correct |
48 |
Correct |
297 ms |
27112 KB |
Output is correct |
49 |
Correct |
312 ms |
29436 KB |
Output is correct |
50 |
Correct |
311 ms |
29292 KB |
Output is correct |
51 |
Correct |
295 ms |
29292 KB |
Output is correct |
52 |
Correct |
174 ms |
27628 KB |
Output is correct |
53 |
Correct |
188 ms |
27628 KB |
Output is correct |
54 |
Correct |
164 ms |
27608 KB |
Output is correct |
55 |
Correct |
178 ms |
27628 KB |
Output is correct |
56 |
Correct |
313 ms |
26220 KB |
Output is correct |
57 |
Correct |
257 ms |
27372 KB |
Output is correct |
58 |
Correct |
263 ms |
27604 KB |
Output is correct |
59 |
Correct |
262 ms |
27500 KB |
Output is correct |
60 |
Correct |
237 ms |
26032 KB |
Output is correct |
61 |
Correct |
266 ms |
27500 KB |
Output is correct |
62 |
Correct |
256 ms |
27184 KB |
Output is correct |
63 |
Correct |
251 ms |
27500 KB |
Output is correct |
64 |
Correct |
262 ms |
26724 KB |
Output is correct |
65 |
Correct |
263 ms |
27756 KB |
Output is correct |