#include <functional>
#include <iostream>
#include <cstring>
#include <vector>
#include <deque>
#include <map>
#include <set>
using namespace std;
const int MAXN = 1e6 + 1e5 + 5;
int n;
int a[MAXN][2];
map <int, set <pair <int, int>>> chainVals;
vector <int> getGreedy()
{
int lastVal = -1;
vector <int> v;
for(int i = 0;i<n;i++)
{
int smallInd = 0, bigInd = 1;
if(a[i][smallInd]>a[i][bigInd]) swap(smallInd, bigInd);
if(lastVal<=a[i][smallInd])
{
v.push_back(smallInd);
lastVal = a[i][smallInd];
}
else if(lastVal<=a[i][bigInd])
{
v.push_back(bigInd);
lastVal = a[i][bigInd];
}
else
{
return {};
}
}
return v;
}
int netChange[MAXN], chain[MAXN];
void doFlip(int i, vector <int> &s)
{
if(i==n) return;
s[i] ^= 1;
if(i!=n-1 && a[i][s[i]]>a[i+1][s[i+1]]) doFlip(i+1, s);
}
bool checkSol(vector <int> &s)
{
int lastVal = -1;
for(int i = 0;i<n;i++)
{
if(lastVal>a[i][s[i]]) return false;
lastVal = a[i][s[i]];
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;n *= 2;
for(int i = 0;i<n;i++) cin >> a[i][0];
for(int i = 0;i<n;i++) cin >> a[i][1];
vector <int> s = getGreedy();
if(s.empty()==true)
{
cout << "-1" << '\n';
return 0;
}
int aCnt = 0;
for(int x: s) aCnt += (x==0);
for(int i = n-1;i>=0;i--)
{
if((i==0 || a[i-1][s[i-1]]<=a[i][s[i]^1]) && (i==n-1 || a[i][s[i]^1]<=a[i+1][s[i+1]]))
{
netChange[i] = ((s[i]==0)?-1:+1);
chain[i] = i;
}
else if((i==0 || a[i-1][s[i-1]]<=a[i][s[i]^1]) && (i==n-1 || a[i][s[i]^1]<=a[i+1][s[i+1]^1]) && chain[i+1]!=-1)
{
netChange[i] = ((s[i]==0)?-1:+1) + netChange[i+1];
chain[i] = chain[i+1];
}
else
{
netChange[i] = 0;
chain[i] = -1;
}
}
/*
cout << '\n';
for(int i = 0;i<n;i++) cout << s[i] << " ";
cout << '\n';
for(int i = 0;i<n;i++) cout << netChange[i] << " ";
cout << '\n';
for(int i = 0;i<n;i++) cout << chain[i] << " ";
cout << '\n';
*/
for(int i = 0;i<n;i++)
{
if(chain[i]!=-1) chainVals[chain[i]].insert({netChange[i], i});
}
for(auto &item: chainVals)
{
if(aCnt>n/2)
{
auto it = item.second.begin();
while(it!=item.second.end())
{
//cout << "k" << '\n';
if(it->first<0 && aCnt + it->first >= n/2)
{
aCnt += it->first;
doFlip(it->second, s);
//cout << " -> flip: " << it->second << '\n';
break;
}
it++;
}
}
else if(aCnt<n/2)
{
auto it = prev(item.second.end());
while(true)
{
if(it->first>0 && aCnt + it->first <= n/2)
{
aCnt += it->first;
doFlip(it->second, s);
//cout << " -> flip: " << it->second << '\n';
break;
}
if(it==item.second.begin()) break;
it--;
}
}
}
if(checkSol(s)==false || aCnt!=n/2)
{
cout << "-1" << '\n';
}
else
{
for(int x: s) cout << char('A'+x);
cout << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
2 ms |
492 KB |
Output is correct |
7 |
Correct |
2 ms |
620 KB |
Output is correct |
8 |
Correct |
2 ms |
876 KB |
Output is correct |
9 |
Correct |
2 ms |
620 KB |
Output is correct |
10 |
Correct |
3 ms |
620 KB |
Output is correct |
11 |
Correct |
2 ms |
492 KB |
Output is correct |
12 |
Correct |
2 ms |
492 KB |
Output is correct |
13 |
Correct |
2 ms |
492 KB |
Output is correct |
14 |
Correct |
3 ms |
1004 KB |
Output is correct |
15 |
Correct |
2 ms |
620 KB |
Output is correct |
16 |
Correct |
2 ms |
620 KB |
Output is correct |
17 |
Correct |
2 ms |
748 KB |
Output is correct |
18 |
Correct |
2 ms |
492 KB |
Output is correct |
19 |
Correct |
2 ms |
492 KB |
Output is correct |
20 |
Correct |
1 ms |
492 KB |
Output is correct |
21 |
Correct |
1 ms |
492 KB |
Output is correct |
22 |
Correct |
2 ms |
1004 KB |
Output is correct |
23 |
Correct |
2 ms |
876 KB |
Output is correct |
24 |
Correct |
2 ms |
620 KB |
Output is correct |
25 |
Correct |
2 ms |
492 KB |
Output is correct |
26 |
Correct |
2 ms |
492 KB |
Output is correct |
27 |
Correct |
2 ms |
620 KB |
Output is correct |
28 |
Correct |
2 ms |
492 KB |
Output is correct |
29 |
Correct |
2 ms |
620 KB |
Output is correct |
30 |
Correct |
2 ms |
492 KB |
Output is correct |
31 |
Correct |
2 ms |
768 KB |
Output is correct |
32 |
Correct |
2 ms |
492 KB |
Output is correct |
33 |
Correct |
2 ms |
568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
2 ms |
492 KB |
Output is correct |
7 |
Correct |
2 ms |
620 KB |
Output is correct |
8 |
Correct |
2 ms |
876 KB |
Output is correct |
9 |
Correct |
2 ms |
620 KB |
Output is correct |
10 |
Correct |
3 ms |
620 KB |
Output is correct |
11 |
Correct |
2 ms |
492 KB |
Output is correct |
12 |
Correct |
2 ms |
492 KB |
Output is correct |
13 |
Correct |
2 ms |
492 KB |
Output is correct |
14 |
Correct |
3 ms |
1004 KB |
Output is correct |
15 |
Correct |
2 ms |
620 KB |
Output is correct |
16 |
Correct |
2 ms |
620 KB |
Output is correct |
17 |
Correct |
2 ms |
748 KB |
Output is correct |
18 |
Correct |
2 ms |
492 KB |
Output is correct |
19 |
Correct |
2 ms |
492 KB |
Output is correct |
20 |
Correct |
1 ms |
492 KB |
Output is correct |
21 |
Correct |
1 ms |
492 KB |
Output is correct |
22 |
Correct |
2 ms |
1004 KB |
Output is correct |
23 |
Correct |
2 ms |
876 KB |
Output is correct |
24 |
Correct |
2 ms |
620 KB |
Output is correct |
25 |
Correct |
2 ms |
492 KB |
Output is correct |
26 |
Correct |
2 ms |
492 KB |
Output is correct |
27 |
Correct |
2 ms |
620 KB |
Output is correct |
28 |
Correct |
2 ms |
492 KB |
Output is correct |
29 |
Correct |
2 ms |
620 KB |
Output is correct |
30 |
Correct |
2 ms |
492 KB |
Output is correct |
31 |
Correct |
2 ms |
768 KB |
Output is correct |
32 |
Correct |
2 ms |
492 KB |
Output is correct |
33 |
Correct |
2 ms |
568 KB |
Output is correct |
34 |
Correct |
218 ms |
8044 KB |
Output is correct |
35 |
Correct |
260 ms |
19548 KB |
Output is correct |
36 |
Correct |
275 ms |
19292 KB |
Output is correct |
37 |
Correct |
264 ms |
19804 KB |
Output is correct |
38 |
Correct |
600 ms |
149468 KB |
Output is correct |
39 |
Correct |
389 ms |
74588 KB |
Output is correct |
40 |
Correct |
455 ms |
86328 KB |
Output is correct |
41 |
Correct |
499 ms |
64604 KB |
Output is correct |
42 |
Correct |
266 ms |
20444 KB |
Output is correct |
43 |
Correct |
285 ms |
21212 KB |
Output is correct |
44 |
Correct |
281 ms |
21212 KB |
Output is correct |
45 |
Correct |
279 ms |
21084 KB |
Output is correct |
46 |
Correct |
648 ms |
162012 KB |
Output is correct |
47 |
Correct |
428 ms |
79836 KB |
Output is correct |
48 |
Correct |
424 ms |
79708 KB |
Output is correct |
49 |
Correct |
458 ms |
86748 KB |
Output is correct |
50 |
Correct |
279 ms |
21084 KB |
Output is correct |
51 |
Correct |
278 ms |
21084 KB |
Output is correct |
52 |
Correct |
210 ms |
21212 KB |
Output is correct |
53 |
Correct |
212 ms |
21108 KB |
Output is correct |
54 |
Correct |
567 ms |
160476 KB |
Output is correct |
55 |
Correct |
451 ms |
126684 KB |
Output is correct |
56 |
Correct |
538 ms |
68188 KB |
Output is correct |
57 |
Correct |
356 ms |
44252 KB |
Output is correct |
58 |
Correct |
353 ms |
44380 KB |
Output is correct |
59 |
Correct |
512 ms |
67952 KB |
Output is correct |
60 |
Correct |
298 ms |
41820 KB |
Output is correct |
61 |
Correct |
329 ms |
44508 KB |
Output is correct |
62 |
Correct |
329 ms |
43868 KB |
Output is correct |
63 |
Correct |
349 ms |
44440 KB |
Output is correct |
64 |
Correct |
314 ms |
43104 KB |
Output is correct |
65 |
Correct |
325 ms |
44568 KB |
Output is correct |