#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
#define sz(u) (int)(u.size())
#define all(u) u.begin(),u.end()
using namespace std;
const int MAXN=5e5;
int n,tmp;
vector<vector<pair<int,int>>> a(2*MAXN);
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
cin>>n;
for(int i=0;i<2*n;i++)
{
cin>>tmp;
a[i].pb({tmp,0});
}
for(int i=0;i<2*n;i++)
{
cin>>tmp;
a[i].pb({tmp,1});
if(a[i][0].x<a[i][1].x) swap(a[i][0],a[i][1]);
}
for(int i=2*n-2;i>=0;i--)
{
if(a[i][0].x>a[i+1][0].x) a[i].erase(a[i].begin());
if(a[i][0].x>a[i+1][0].x) a[i].erase(a[i].begin());
if(sz(a[i])==0)
{
cout<<-1;
return 0;
}
}
for(int i=1;i<2*n;i++)
if(a[i].back().x<a[i-1].back().x) a[i].erase(prev(a[i].end()));
string ans="";
int cnt=0;
for(int i=0;i<2*n;i++) ans+='A'+a[i][0].y, cnt+=a[i][0].y;
int need=cnt<n;
int left=abs(n-cnt), late=0;
int newstart=0;
for(int i=0;i<2*n && left;i++)
{
if(sz(a[i])!=2)
{
newstart=i+1;
late=0;
continue;
}
if(i) if(a[i][1].x>=a[i-1][0].x) newstart=i, late=0;
if(a[i][1].y==need)
{
late++;
if(late>=0)
{
for(int j=newstart;j<=i;j++) ans[j]='A'+a[j][1].y;
newstart=i+1;
left-=late;
late=0;
}
}
else late--;
}
if(left) cout<<-1;
else cout<<ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23808 KB |
Output is correct |
2 |
Correct |
18 ms |
23808 KB |
Output is correct |
3 |
Correct |
17 ms |
23936 KB |
Output is correct |
4 |
Correct |
18 ms |
23808 KB |
Output is correct |
5 |
Correct |
19 ms |
24064 KB |
Output is correct |
6 |
Correct |
19 ms |
24064 KB |
Output is correct |
7 |
Correct |
18 ms |
24064 KB |
Output is correct |
8 |
Correct |
19 ms |
24064 KB |
Output is correct |
9 |
Correct |
20 ms |
24064 KB |
Output is correct |
10 |
Correct |
19 ms |
23936 KB |
Output is correct |
11 |
Correct |
19 ms |
24064 KB |
Output is correct |
12 |
Correct |
19 ms |
24064 KB |
Output is correct |
13 |
Correct |
19 ms |
24064 KB |
Output is correct |
14 |
Correct |
19 ms |
24064 KB |
Output is correct |
15 |
Correct |
19 ms |
24064 KB |
Output is correct |
16 |
Correct |
20 ms |
24064 KB |
Output is correct |
17 |
Correct |
20 ms |
24040 KB |
Output is correct |
18 |
Correct |
18 ms |
24064 KB |
Output is correct |
19 |
Correct |
19 ms |
24064 KB |
Output is correct |
20 |
Correct |
20 ms |
24056 KB |
Output is correct |
21 |
Correct |
19 ms |
24064 KB |
Output is correct |
22 |
Correct |
19 ms |
24064 KB |
Output is correct |
23 |
Correct |
19 ms |
24064 KB |
Output is correct |
24 |
Correct |
20 ms |
24064 KB |
Output is correct |
25 |
Correct |
19 ms |
24064 KB |
Output is correct |
26 |
Correct |
18 ms |
24064 KB |
Output is correct |
27 |
Correct |
18 ms |
24064 KB |
Output is correct |
28 |
Correct |
18 ms |
23936 KB |
Output is correct |
29 |
Correct |
18 ms |
24064 KB |
Output is correct |
30 |
Correct |
19 ms |
24064 KB |
Output is correct |
31 |
Correct |
18 ms |
24064 KB |
Output is correct |
32 |
Correct |
18 ms |
23936 KB |
Output is correct |
33 |
Correct |
19 ms |
24064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23808 KB |
Output is correct |
2 |
Correct |
18 ms |
23808 KB |
Output is correct |
3 |
Correct |
17 ms |
23936 KB |
Output is correct |
4 |
Correct |
18 ms |
23808 KB |
Output is correct |
5 |
Correct |
19 ms |
24064 KB |
Output is correct |
6 |
Correct |
19 ms |
24064 KB |
Output is correct |
7 |
Correct |
18 ms |
24064 KB |
Output is correct |
8 |
Correct |
19 ms |
24064 KB |
Output is correct |
9 |
Correct |
20 ms |
24064 KB |
Output is correct |
10 |
Correct |
19 ms |
23936 KB |
Output is correct |
11 |
Correct |
19 ms |
24064 KB |
Output is correct |
12 |
Correct |
19 ms |
24064 KB |
Output is correct |
13 |
Correct |
19 ms |
24064 KB |
Output is correct |
14 |
Correct |
19 ms |
24064 KB |
Output is correct |
15 |
Correct |
19 ms |
24064 KB |
Output is correct |
16 |
Correct |
20 ms |
24064 KB |
Output is correct |
17 |
Correct |
20 ms |
24040 KB |
Output is correct |
18 |
Correct |
18 ms |
24064 KB |
Output is correct |
19 |
Correct |
19 ms |
24064 KB |
Output is correct |
20 |
Correct |
20 ms |
24056 KB |
Output is correct |
21 |
Correct |
19 ms |
24064 KB |
Output is correct |
22 |
Correct |
19 ms |
24064 KB |
Output is correct |
23 |
Correct |
19 ms |
24064 KB |
Output is correct |
24 |
Correct |
20 ms |
24064 KB |
Output is correct |
25 |
Correct |
19 ms |
24064 KB |
Output is correct |
26 |
Correct |
18 ms |
24064 KB |
Output is correct |
27 |
Correct |
18 ms |
24064 KB |
Output is correct |
28 |
Correct |
18 ms |
23936 KB |
Output is correct |
29 |
Correct |
18 ms |
24064 KB |
Output is correct |
30 |
Correct |
19 ms |
24064 KB |
Output is correct |
31 |
Correct |
18 ms |
24064 KB |
Output is correct |
32 |
Correct |
18 ms |
23936 KB |
Output is correct |
33 |
Correct |
19 ms |
24064 KB |
Output is correct |
34 |
Correct |
419 ms |
55056 KB |
Output is correct |
35 |
Correct |
411 ms |
55044 KB |
Output is correct |
36 |
Correct |
403 ms |
54576 KB |
Output is correct |
37 |
Correct |
421 ms |
55216 KB |
Output is correct |
38 |
Correct |
413 ms |
55276 KB |
Output is correct |
39 |
Correct |
407 ms |
55344 KB |
Output is correct |
40 |
Correct |
432 ms |
57456 KB |
Output is correct |
41 |
Correct |
411 ms |
55984 KB |
Output is correct |
42 |
Correct |
426 ms |
56368 KB |
Output is correct |
43 |
Correct |
439 ms |
57732 KB |
Output is correct |
44 |
Correct |
444 ms |
57836 KB |
Output is correct |
45 |
Correct |
447 ms |
62496 KB |
Output is correct |
46 |
Correct |
447 ms |
62356 KB |
Output is correct |
47 |
Correct |
466 ms |
75680 KB |
Output is correct |
48 |
Correct |
466 ms |
75520 KB |
Output is correct |
49 |
Correct |
433 ms |
60396 KB |
Output is correct |
50 |
Correct |
470 ms |
75880 KB |
Output is correct |
51 |
Correct |
453 ms |
75852 KB |
Output is correct |
52 |
Correct |
339 ms |
65004 KB |
Output is correct |
53 |
Correct |
342 ms |
65004 KB |
Output is correct |
54 |
Correct |
319 ms |
64876 KB |
Output is correct |
55 |
Correct |
322 ms |
64620 KB |
Output is correct |
56 |
Correct |
470 ms |
76952 KB |
Output is correct |
57 |
Correct |
409 ms |
71596 KB |
Output is correct |
58 |
Correct |
421 ms |
71916 KB |
Output is correct |
59 |
Correct |
423 ms |
71916 KB |
Output is correct |
60 |
Correct |
406 ms |
69420 KB |
Output is correct |
61 |
Correct |
434 ms |
72428 KB |
Output is correct |
62 |
Correct |
433 ms |
71660 KB |
Output is correct |
63 |
Correct |
434 ms |
72380 KB |
Output is correct |
64 |
Correct |
408 ms |
70704 KB |
Output is correct |
65 |
Correct |
434 ms |
72300 KB |
Output is correct |