#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int n, l[maxn][2];
void input()
{
cin >> n;
n *= 2;
for (int i = 1; i <= n; i ++)
cin >> l[i][0];
for (int i = 1; i <= n; i ++)
cin >> l[i][1];
}
int dp[maxn][2], from[maxn][2];
string get_max(int c)
{
for (int i = 1; i <= n; i ++)
{
dp[i][0] = dp[i][1] = -1e9;
from[i][0] = from[i][1] = -1;
}
dp[1][c] = 1;
dp[1][(1 + c) % 2] = 0;
///cout << "--------------" << endl;
for (int i = 2; i <= n; i ++)
{
for (int t = 0; t < 2; t ++)
for (int d = 0; d < 2; d ++)
{
if (l[i - 1][t] <= l[i][d])
{
int val = dp[i - 1][t] + (d == c);
if (val > dp[i][d])
{
from[i][d] = t;
dp[i][d] = val;
}
}
}
///cout << dp[i][0] << " " << dp[i][1] << endl;
}
string res = "";
if (dp[n][0] < 0 && dp[n][1] < 0)
return res;
int row = n, state = 0;
if (dp[n][1] > dp[n][0])
state = 1;
while(row > 1)
{
///cout << state << endl;
int val = l[row][state];
int bef = l[row - 1][from[row][state]];
assert(bef <= val);
if (state == 0)
res.push_back('A');
else
res.push_back('B');
state = from[row][state];
row --;
}
if (state == 0)
res.push_back('A');
else
res.push_back('B');
reverse(res.begin(), res.end());
return res;
}
bool can_swap(string &a, int &b, int pos)
{
int val = l[pos + 1][0];
if (a[pos] == 'A')
val = l[pos + 1][1];
if (pos > 0)
{
int bef = l[pos][0];
if (a[pos - 1] == 'B')
bef = l[pos][1];
if (bef > val)
return false;
}
if (pos + 1 < a.size())
{
int nxt = l[pos + 2][0];
if (a[pos + 1] == 'B')
nxt = l[pos + 2][1];
if (nxt < val)
return false;
}
if (a[pos] == 'A')
{
a[pos] = 'B';
b -= 2;
}
else
{
a[pos] = 'A';
b += 2;
}
return true;
}
bool can_change(int pos, string &a)
{
int val = l[pos + 1][0];
if (a[pos] == 'A')
val = l[pos + 1][1];
if (pos > 0)
{
int bef = l[pos][0];
if (a[pos - 1] == 'B')
bef = l[pos][1];
if (bef > val)
return false;
}
if (pos + 1 < a.size())
{
int nxt = l[pos + 2][0];
if (a[pos + 1] == 'B')
nxt = l[pos + 2][1];
if (nxt < val)
return false;
}
return true;
}
set < int > act;
void check_to_change(int pos, string &a, string &b)
{
if (pos < 0 || pos == n)
return;
if (a[pos] == b[pos])
return;
if (can_change(pos, a))
{
act.insert(pos);
}
else
{
if (act.find(pos) != act.end())
act.erase(pos);
}
}
void simulate()
{
string a = get_max(0);
string b = get_max(1);
if (a.empty() || b.empty())
{
cout << -1 << endl;
return;
}
int balance = 0;
for (int i = 0; i < a.size(); i ++)
{
if (a[i] == 'A')
balance ++;
else
balance --;
}
/***/
int bl = 0;
for (int i = 0; i < b.size(); i ++)
{
if (b[i] == 'A')
bl ++;
else
bl --;
}
assert(balance % 2 == 0 && bl % 2 == 0);
for (int i = 0; i < n; i ++)
check_to_change(i, a, b);
while(balance != 0)
{
if (act.empty())
break;
int val = *act.begin();
act.erase(val);
assert(can_swap(a, balance, val));
check_to_change(val - 1, a, b);
check_to_change(val, a, b);
check_to_change(val + 1, a, b);
}
///int lf = 0, rf = (int)(a.size()) - 1;
if (balance != 0)
cout << -1 << endl;
else
{
assert(n == a.size());
int cnt = 0, cnt2 = 0;
for (int i = 0; i < n; i ++)
if (a[i] == 'A')
cnt ++;
else
if (a[i] == 'B')
cnt2 ++;
assert(cnt == n / 2 && cnt2 == n / 2);
for (int i = 1; i < n; i ++)
{
int val = l[i + 1][0];
if (a[i] == 'B')
val = l[i + 1][1];
int bef = l[i][0];
if (a[i - 1] == 'B')
bef = l[i][1];
assert(bef <= val);
}
cout << a << endl;
}
}
void solve()
{
input();
simulate();
}
int main()
{
solve();
return 0;
}
Compilation message
building4.cpp: In function 'bool can_swap(std::string&, int&, int)':
building4.cpp:104:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | if (pos + 1 < a.size())
| ~~~~~~~~^~~~~~~~~~
building4.cpp: In function 'bool can_change(int, std::string&)':
building4.cpp:143:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | if (pos + 1 < a.size())
| ~~~~~~~~^~~~~~~~~~
building4.cpp: In function 'void simulate()':
building4.cpp:187:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
187 | for (int i = 0; i < a.size(); i ++)
| ~~^~~~~~~~~~
building4.cpp:197:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
197 | for (int i = 0; i < b.size(); i ++)
| ~~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from building4.cpp:1:
building4.cpp:229:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
229 | assert(n == a.size());
| ~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4440 KB |
Output is correct |
5 |
Correct |
3 ms |
4444 KB |
Output is correct |
6 |
Correct |
3 ms |
4544 KB |
Output is correct |
7 |
Correct |
3 ms |
4444 KB |
Output is correct |
8 |
Correct |
5 ms |
4700 KB |
Output is correct |
9 |
Correct |
3 ms |
4552 KB |
Output is correct |
10 |
Correct |
3 ms |
4444 KB |
Output is correct |
11 |
Correct |
3 ms |
4444 KB |
Output is correct |
12 |
Correct |
3 ms |
4440 KB |
Output is correct |
13 |
Correct |
4 ms |
4444 KB |
Output is correct |
14 |
Correct |
4 ms |
4952 KB |
Output is correct |
15 |
Correct |
3 ms |
4700 KB |
Output is correct |
16 |
Correct |
3 ms |
4700 KB |
Output is correct |
17 |
Correct |
5 ms |
4708 KB |
Output is correct |
18 |
Correct |
3 ms |
4444 KB |
Output is correct |
19 |
Correct |
3 ms |
4444 KB |
Output is correct |
20 |
Correct |
2 ms |
4444 KB |
Output is correct |
21 |
Correct |
2 ms |
4444 KB |
Output is correct |
22 |
Correct |
3 ms |
4700 KB |
Output is correct |
23 |
Correct |
2 ms |
4700 KB |
Output is correct |
24 |
Correct |
3 ms |
4444 KB |
Output is correct |
25 |
Correct |
2 ms |
4444 KB |
Output is correct |
26 |
Correct |
3 ms |
4444 KB |
Output is correct |
27 |
Correct |
2 ms |
4444 KB |
Output is correct |
28 |
Correct |
2 ms |
4444 KB |
Output is correct |
29 |
Correct |
2 ms |
4696 KB |
Output is correct |
30 |
Correct |
2 ms |
4444 KB |
Output is correct |
31 |
Correct |
3 ms |
4444 KB |
Output is correct |
32 |
Correct |
2 ms |
4444 KB |
Output is correct |
33 |
Correct |
2 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4440 KB |
Output is correct |
5 |
Correct |
3 ms |
4444 KB |
Output is correct |
6 |
Correct |
3 ms |
4544 KB |
Output is correct |
7 |
Correct |
3 ms |
4444 KB |
Output is correct |
8 |
Correct |
5 ms |
4700 KB |
Output is correct |
9 |
Correct |
3 ms |
4552 KB |
Output is correct |
10 |
Correct |
3 ms |
4444 KB |
Output is correct |
11 |
Correct |
3 ms |
4444 KB |
Output is correct |
12 |
Correct |
3 ms |
4440 KB |
Output is correct |
13 |
Correct |
4 ms |
4444 KB |
Output is correct |
14 |
Correct |
4 ms |
4952 KB |
Output is correct |
15 |
Correct |
3 ms |
4700 KB |
Output is correct |
16 |
Correct |
3 ms |
4700 KB |
Output is correct |
17 |
Correct |
5 ms |
4708 KB |
Output is correct |
18 |
Correct |
3 ms |
4444 KB |
Output is correct |
19 |
Correct |
3 ms |
4444 KB |
Output is correct |
20 |
Correct |
2 ms |
4444 KB |
Output is correct |
21 |
Correct |
2 ms |
4444 KB |
Output is correct |
22 |
Correct |
3 ms |
4700 KB |
Output is correct |
23 |
Correct |
2 ms |
4700 KB |
Output is correct |
24 |
Correct |
3 ms |
4444 KB |
Output is correct |
25 |
Correct |
2 ms |
4444 KB |
Output is correct |
26 |
Correct |
3 ms |
4444 KB |
Output is correct |
27 |
Correct |
2 ms |
4444 KB |
Output is correct |
28 |
Correct |
2 ms |
4444 KB |
Output is correct |
29 |
Correct |
2 ms |
4696 KB |
Output is correct |
30 |
Correct |
2 ms |
4444 KB |
Output is correct |
31 |
Correct |
3 ms |
4444 KB |
Output is correct |
32 |
Correct |
2 ms |
4444 KB |
Output is correct |
33 |
Correct |
2 ms |
4444 KB |
Output is correct |
34 |
Correct |
568 ms |
33368 KB |
Output is correct |
35 |
Correct |
561 ms |
35272 KB |
Output is correct |
36 |
Correct |
552 ms |
34760 KB |
Output is correct |
37 |
Correct |
568 ms |
35264 KB |
Output is correct |
38 |
Correct |
766 ms |
78536 KB |
Output is correct |
39 |
Correct |
596 ms |
45884 KB |
Output is correct |
40 |
Correct |
673 ms |
49688 KB |
Output is correct |
41 |
Correct |
551 ms |
35276 KB |
Output is correct |
42 |
Correct |
579 ms |
36036 KB |
Output is correct |
43 |
Correct |
627 ms |
37640 KB |
Output is correct |
44 |
Correct |
611 ms |
37700 KB |
Output is correct |
45 |
Correct |
613 ms |
37752 KB |
Output is correct |
46 |
Correct |
835 ms |
83820 KB |
Output is correct |
47 |
Correct |
626 ms |
48152 KB |
Output is correct |
48 |
Correct |
637 ms |
48000 KB |
Output is correct |
49 |
Correct |
669 ms |
49796 KB |
Output is correct |
50 |
Correct |
593 ms |
37052 KB |
Output is correct |
51 |
Correct |
603 ms |
37244 KB |
Output is correct |
52 |
Correct |
361 ms |
31880 KB |
Output is correct |
53 |
Correct |
353 ms |
31812 KB |
Output is correct |
54 |
Correct |
600 ms |
77272 KB |
Output is correct |
55 |
Correct |
534 ms |
65848 KB |
Output is correct |
56 |
Correct |
643 ms |
37760 KB |
Output is correct |
57 |
Correct |
511 ms |
35144 KB |
Output is correct |
58 |
Correct |
542 ms |
35136 KB |
Output is correct |
59 |
Correct |
503 ms |
35200 KB |
Output is correct |
60 |
Correct |
482 ms |
40392 KB |
Output is correct |
61 |
Correct |
503 ms |
42824 KB |
Output is correct |
62 |
Correct |
495 ms |
42396 KB |
Output is correct |
63 |
Correct |
538 ms |
42760 KB |
Output is correct |
64 |
Correct |
487 ms |
41108 KB |
Output is correct |
65 |
Correct |
517 ms |
42652 KB |
Output is correct |