#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
const int N = 1055555;
int a[2][N+1];
ii dp[N+1][2];
//int dp[5555][5555];
void uni(ii &a, ii b)
{
a.fi=min(a.fi,b.fi);
a.se=max(a.se,b.se);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n; cin>>n; n*=2;
const bool DEBUG = 0;
for(int cc=1;;cc++)
{
if(!DEBUG)
{
for(int i=0;i<n;i++)
{
cin>>a[0][i];
}
for(int i=0;i<n;i++)
{
cin>>a[1][i];
}
}
else
{
for(int i=0;i<n;i++)
{
a[0][i]=rand();
a[1][i]=rand();
}
}
/*
for(int i=0;i<n;i++)
{
for(int j=0;j<=n;j++)
{
dp[i][j]=int(1e9)+7;
}
}
dp[0][1]=a[0][0];
dp[0][0]=a[1][0];
for(int i=1;i<n;i++)
{
for(int j=0;j<=i+1;j++)
{
//choose a
if(j&&dp[i-1][j-1]<=a[0][i]) dp[i][j]=min(dp[i][j],a[0][i]);
if(dp[i-1][j]<=a[1][i]) dp[i][j]=min(dp[i][j],a[1][i]);
}
int l=int(1e9);
int r=0;
int cnt=0;
for(int j=0;j<=i+1;j++)
{
if(dp[i][j]<int(1e9)+7)
{
l=min(l,j); r=max(r,j); cnt++;
}
}
if(l>r) l=r+1;
assert(cnt==r-l+1);
}
*/
dp[0][0]={0,0};
dp[0][1]={1,1};
for(int i=1;i<n;i++)
{
for(int j=0;j<2;j++)
{
dp[i][j]={int(1e9),-int(1e9)};
//use a[j][i]
for(int k=0;k<2;k++)
{
if(dp[i-1][k].fi>dp[i-1][k].se) continue;
if(a[k][i-1]<=a[j][i]) uni(dp[i][j],{dp[i-1][k].fi+j,dp[i-1][k].se+j});
}
//cerr<<i<<' '<<j<<' '<<dp[i][j].fi<<' '<<dp[i][j].se<<'\n';
}
}
int endpos=-1;
for(int i=0;i<2;i++)
{
if(dp[n-1][i].fi<=n/2&&dp[n-1][i].se>=n/2)
{
endpos=i; break;
}
}
if(endpos==-1)
{
cout<<endpos<<'\n';
}
else
{
string s;
int cnt=n/2;
for(int i=n-1;i>=0;i--)
{
s+=char('A'+endpos);
cnt-=endpos;
if(i>0)
{
//look at dp[endpos][i]
int pos=0;
for(int j=0;j<2;j++)
{
if(dp[i-1][j].fi<=cnt&&cnt<=dp[i-1][j].se&&a[j][i-1]<=a[endpos][i])
{
endpos=j; pos=1;
break;
}
}
assert(pos);
}
}
reverse(s.begin(),s.end());
cout<<s<<'\n';
}
if(DEBUG)
{
cerr<<"Case #"<<cc<<" completed\n";
}
else return 0;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 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 |
560 KB |
Output is correct |
9 |
Correct |
6 ms |
512 KB |
Output is correct |
10 |
Correct |
6 ms |
512 KB |
Output is correct |
11 |
Correct |
6 ms |
512 KB |
Output is correct |
12 |
Correct |
6 ms |
512 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 |
640 KB |
Output is correct |
19 |
Correct |
6 ms |
512 KB |
Output is correct |
20 |
Correct |
5 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 |
5 ms |
512 KB |
Output is correct |
24 |
Correct |
6 ms |
512 KB |
Output is correct |
25 |
Correct |
6 ms |
512 KB |
Output is correct |
26 |
Correct |
5 ms |
512 KB |
Output is correct |
27 |
Correct |
6 ms |
512 KB |
Output is correct |
28 |
Correct |
5 ms |
512 KB |
Output is correct |
29 |
Correct |
6 ms |
512 KB |
Output is correct |
30 |
Correct |
5 ms |
512 KB |
Output is correct |
31 |
Correct |
6 ms |
512 KB |
Output is correct |
32 |
Correct |
5 ms |
512 KB |
Output is correct |
33 |
Correct |
6 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 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 |
560 KB |
Output is correct |
9 |
Correct |
6 ms |
512 KB |
Output is correct |
10 |
Correct |
6 ms |
512 KB |
Output is correct |
11 |
Correct |
6 ms |
512 KB |
Output is correct |
12 |
Correct |
6 ms |
512 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 |
640 KB |
Output is correct |
19 |
Correct |
6 ms |
512 KB |
Output is correct |
20 |
Correct |
5 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 |
5 ms |
512 KB |
Output is correct |
24 |
Correct |
6 ms |
512 KB |
Output is correct |
25 |
Correct |
6 ms |
512 KB |
Output is correct |
26 |
Correct |
5 ms |
512 KB |
Output is correct |
27 |
Correct |
6 ms |
512 KB |
Output is correct |
28 |
Correct |
5 ms |
512 KB |
Output is correct |
29 |
Correct |
6 ms |
512 KB |
Output is correct |
30 |
Correct |
5 ms |
512 KB |
Output is correct |
31 |
Correct |
6 ms |
512 KB |
Output is correct |
32 |
Correct |
5 ms |
512 KB |
Output is correct |
33 |
Correct |
6 ms |
512 KB |
Output is correct |
34 |
Correct |
309 ms |
42448 KB |
Output is correct |
35 |
Correct |
299 ms |
25592 KB |
Output is correct |
36 |
Correct |
294 ms |
24496 KB |
Output is correct |
37 |
Correct |
306 ms |
28720 KB |
Output is correct |
38 |
Correct |
296 ms |
29476 KB |
Output is correct |
39 |
Correct |
285 ms |
26032 KB |
Output is correct |
40 |
Correct |
310 ms |
44780 KB |
Output is correct |
41 |
Correct |
281 ms |
25648 KB |
Output is correct |
42 |
Correct |
324 ms |
43760 KB |
Output is correct |
43 |
Correct |
309 ms |
38764 KB |
Output is correct |
44 |
Correct |
328 ms |
39532 KB |
Output is correct |
45 |
Correct |
315 ms |
41836 KB |
Output is correct |
46 |
Correct |
311 ms |
38508 KB |
Output is correct |
47 |
Correct |
315 ms |
26976 KB |
Output is correct |
48 |
Correct |
296 ms |
43884 KB |
Output is correct |
49 |
Correct |
326 ms |
40556 KB |
Output is correct |
50 |
Correct |
320 ms |
44452 KB |
Output is correct |
51 |
Correct |
323 ms |
44520 KB |
Output is correct |
52 |
Correct |
190 ms |
33516 KB |
Output is correct |
53 |
Correct |
186 ms |
33644 KB |
Output is correct |
54 |
Correct |
172 ms |
33724 KB |
Output is correct |
55 |
Correct |
179 ms |
33260 KB |
Output is correct |
56 |
Correct |
306 ms |
41324 KB |
Output is correct |
57 |
Correct |
281 ms |
40432 KB |
Output is correct |
58 |
Correct |
284 ms |
40532 KB |
Output is correct |
59 |
Correct |
276 ms |
40556 KB |
Output is correct |
60 |
Correct |
257 ms |
38448 KB |
Output is correct |
61 |
Correct |
283 ms |
40844 KB |
Output is correct |
62 |
Correct |
278 ms |
40552 KB |
Output is correct |
63 |
Correct |
273 ms |
40712 KB |
Output is correct |
64 |
Correct |
263 ms |
39468 KB |
Output is correct |
65 |
Correct |
270 ms |
40684 KB |
Output is correct |