#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define ff first
#define ss second
#define N 1050000
#define MOD 998244353
#define INF 0x3f3f3f3f
int a[N][2];
int dp[N][2][2];
void update(int i, int j, int mn, int mx){
if(mx == -1) return;
if(dp[i][j][0] == -1){
dp[i][j][0] = mn + j;
dp[i][j][1] = mx + j;
return;
}
dp[i][j][0] = min(dp[i][j][0], mn + j);
dp[i][j][1] = max(dp[i][j][1], mx + j);
}
int ans[N];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i = 1; i <= n * 2; ++i)
cin>>a[i][0];
for(int i = 1; i <= n * 2; ++i)
cin>>a[i][1];
memset(dp, -1, sizeof dp);
memset(dp[0], 0, sizeof dp[0]);
for(int i = 1; i <= n * 2; ++i){
for(int j0 = 0; j0 < 2; ++j0){
for(int j1 = 0; j1 < 2; ++j1){
if(a[i][j1] >= a[i - 1][j0])
update(i, j1, dp[i - 1][j0][0], dp[i - 1][j0][1]);
}
}
}
int la = -1, c = n;
if(dp[2 * n][0][0] <= c && c <= dp[2 * n][0][1])
la = 0;
if(dp[2 * n][1][0] <= c && c <= dp[2 * n][1][1])
la = 1;
if(la == -1){
cout<<-1;
return 0;
}
for(int i = n * 2; i >= 0; --i){
ans[i] = la;
c -= la;
for(int j = 0; j < 2; ++j){
if(a[i - 1][j] <= a[i][la]){
if(dp[i - 1][j][0] <= c && c <= dp[i - 1][j][1]){
la = j;
break;
}
}
}
}
for(int i = 1; i <= 2 * n; ++i)
cout<<(ans[i] == 0 ? "A" : "B");
}
Compilation message
building4.cpp: In function 'int main()':
building4.cpp:49:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(dp[2 * n][0][0] <= c && c <= dp[2 * n][0][1])
^~
building4.cpp:52:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if(dp[2 * n][1][0] <= c && c <= dp[2 * n][1][1])
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 2 |
Correct |
13 ms |
16768 KB |
Output is correct |
| 3 |
Correct |
16 ms |
16768 KB |
Output is correct |
| 4 |
Correct |
13 ms |
16768 KB |
Output is correct |
| 5 |
Correct |
15 ms |
16896 KB |
Output is correct |
| 6 |
Correct |
26 ms |
16896 KB |
Output is correct |
| 7 |
Correct |
18 ms |
16896 KB |
Output is correct |
| 8 |
Correct |
18 ms |
16896 KB |
Output is correct |
| 9 |
Correct |
16 ms |
16896 KB |
Output is correct |
| 10 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 11 |
Correct |
19 ms |
16896 KB |
Output is correct |
| 12 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 13 |
Correct |
16 ms |
16896 KB |
Output is correct |
| 14 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 15 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 16 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 17 |
Correct |
15 ms |
16896 KB |
Output is correct |
| 18 |
Correct |
17 ms |
16896 KB |
Output is correct |
| 19 |
Correct |
17 ms |
16896 KB |
Output is correct |
| 20 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 21 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 22 |
Correct |
13 ms |
16896 KB |
Output is correct |
| 23 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 24 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 25 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 26 |
Correct |
13 ms |
16896 KB |
Output is correct |
| 27 |
Correct |
13 ms |
16896 KB |
Output is correct |
| 28 |
Correct |
13 ms |
16896 KB |
Output is correct |
| 29 |
Correct |
13 ms |
16896 KB |
Output is correct |
| 30 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 31 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 32 |
Correct |
13 ms |
16896 KB |
Output is correct |
| 33 |
Correct |
13 ms |
16896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 2 |
Correct |
13 ms |
16768 KB |
Output is correct |
| 3 |
Correct |
16 ms |
16768 KB |
Output is correct |
| 4 |
Correct |
13 ms |
16768 KB |
Output is correct |
| 5 |
Correct |
15 ms |
16896 KB |
Output is correct |
| 6 |
Correct |
26 ms |
16896 KB |
Output is correct |
| 7 |
Correct |
18 ms |
16896 KB |
Output is correct |
| 8 |
Correct |
18 ms |
16896 KB |
Output is correct |
| 9 |
Correct |
16 ms |
16896 KB |
Output is correct |
| 10 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 11 |
Correct |
19 ms |
16896 KB |
Output is correct |
| 12 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 13 |
Correct |
16 ms |
16896 KB |
Output is correct |
| 14 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 15 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 16 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 17 |
Correct |
15 ms |
16896 KB |
Output is correct |
| 18 |
Correct |
17 ms |
16896 KB |
Output is correct |
| 19 |
Correct |
17 ms |
16896 KB |
Output is correct |
| 20 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 21 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 22 |
Correct |
13 ms |
16896 KB |
Output is correct |
| 23 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 24 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 25 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 26 |
Correct |
13 ms |
16896 KB |
Output is correct |
| 27 |
Correct |
13 ms |
16896 KB |
Output is correct |
| 28 |
Correct |
13 ms |
16896 KB |
Output is correct |
| 29 |
Correct |
13 ms |
16896 KB |
Output is correct |
| 30 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 31 |
Correct |
14 ms |
16896 KB |
Output is correct |
| 32 |
Correct |
13 ms |
16896 KB |
Output is correct |
| 33 |
Correct |
13 ms |
16896 KB |
Output is correct |
| 34 |
Correct |
313 ms |
26720 KB |
Output is correct |
| 35 |
Correct |
335 ms |
34168 KB |
Output is correct |
| 36 |
Correct |
339 ms |
34604 KB |
Output is correct |
| 37 |
Correct |
361 ms |
33912 KB |
Output is correct |
| 38 |
Correct |
361 ms |
33812 KB |
Output is correct |
| 39 |
Correct |
324 ms |
37500 KB |
Output is correct |
| 40 |
Correct |
375 ms |
31524 KB |
Output is correct |
| 41 |
Correct |
352 ms |
37880 KB |
Output is correct |
| 42 |
Correct |
371 ms |
31224 KB |
Output is correct |
| 43 |
Correct |
378 ms |
31736 KB |
Output is correct |
| 44 |
Correct |
389 ms |
31864 KB |
Output is correct |
| 45 |
Correct |
352 ms |
34168 KB |
Output is correct |
| 46 |
Correct |
343 ms |
31608 KB |
Output is correct |
| 47 |
Correct |
355 ms |
36472 KB |
Output is correct |
| 48 |
Correct |
336 ms |
32888 KB |
Output is correct |
| 49 |
Correct |
348 ms |
31408 KB |
Output is correct |
| 50 |
Correct |
366 ms |
31480 KB |
Output is correct |
| 51 |
Correct |
363 ms |
31480 KB |
Output is correct |
| 52 |
Correct |
235 ms |
37112 KB |
Output is correct |
| 53 |
Correct |
241 ms |
37112 KB |
Output is correct |
| 54 |
Correct |
263 ms |
37240 KB |
Output is correct |
| 55 |
Correct |
231 ms |
36852 KB |
Output is correct |
| 56 |
Correct |
367 ms |
31864 KB |
Output is correct |
| 57 |
Correct |
358 ms |
43880 KB |
Output is correct |
| 58 |
Correct |
365 ms |
44024 KB |
Output is correct |
| 59 |
Correct |
323 ms |
44004 KB |
Output is correct |
| 60 |
Correct |
307 ms |
42744 KB |
Output is correct |
| 61 |
Correct |
340 ms |
44536 KB |
Output is correct |
| 62 |
Correct |
360 ms |
44152 KB |
Output is correct |
| 63 |
Correct |
359 ms |
44276 KB |
Output is correct |
| 64 |
Correct |
329 ms |
43640 KB |
Output is correct |
| 65 |
Correct |
321 ms |
44016 KB |
Output is correct |
