#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef tuple<int, int, int> tiii;
typedef tuple<int, int, int, int> tiiii;
typedef set <int> si;
typedef map <int, int> mii;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <vector <int>> vvi;
#define F(i, a, b) for(int i = a; i <= (int)b; i++)
#define f(i, a, b) for(int i = a; i >= (int)b; i--)
#define F2(i, a, b) for(int i = a; i <= (int)b; i+=2)
#define f2(i, a, b) for(int i = a; i >= (int)b; i-=2)
#define wh(n) int iteration = n; while(iteration--)
#define For(t, it) for(auto it = (t).begin(); it != (t).end(); ++it)
#define IN insert
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define RS resize
#define uset unordered_set
#define umap unordered_map
#define GRAF(n) vvi gr; gr.resize(n+1); vector <bool> was(n+1, 0);
ld const PI = acos(-1);
int const N = 1e6 + 7, inf = 1e9 + 7;
int a[2][N], ans[N], cnt[2];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
F(i, 0, 1)
F(j, 1, 2*n)
cin >> a[i][j];
ans[0] = a[0][0] = 0;
ans[2*n+1] = 0, a[0][2*n+1] = inf;
F(i, 1, 2*n){
int mx = inf, pos = -1;
F(j, 0, 1)
if(a[j][i] >= a[ans[i-1]][i-1] && a[j][i] < mx)
mx = a[j][i], pos = j;
if(pos == -1){
cout << -1;
return 0;
}
ans[i] = pos;
cnt[pos]++;
}
f(i, 2*n, 1){
if(cnt[ans[i]] <= n)
continue;
if(a[!ans[i]][i] >= a[ans[i]][i] && a[!ans[i]][i] <= a[ans[i+1]][i+1]){
cnt[ans[i]]--;
ans[i] ^= 1;
cnt[ans[i]]++;
}
}
if(cnt[0] != cnt[1]){
cout << -1;
return 0;
}
F(i, 1, 2*n)
cout << char('A' + ans[i]);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
8 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 |
512 KB |
Output is correct |
| 9 |
Incorrect |
5 ms |
512 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
8 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 |
512 KB |
Output is correct |
| 9 |
Incorrect |
5 ms |
512 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
