# Untitled

unknown
c_cpp
2 years ago
1.8 kB
1
Indexable
Never
```//Solution by Tima
#include <bits/stdc++.h>

#define f first
#define s second
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define pb push_back
#define vi vector <int>
#define ld long double
#define pii pair<int, int>
#define y1 sda
#define all(x) x.begin(), x.end()

using namespace std;
const int N = int(2e6) + 12, mod = int(1e9)  + 7;

int n, c[N], cnt[2], d[N];
multiset <int> st;

char s[N];
int nxt[N], prv[N], num[N];
int pos[N];

ll sum;
int a,b;

inline void del(int x){
int i = pos[x];
pos[x]--;
int r = nxt[i], l = prv[i];
nxt[l] = r;
prv[r] = l;
}

void solve(){
scanf("%d", &n);

for(int i = 1; i <= n; i++){
scanf("%d", &c[i]);
num[c[i]]++;
sum += c[i];
}

// a * b = c[1] + c[2] + ... + c[n], a + b = n

bool found = 0;

for(int i = 0; i <= n; i++){
a = i, b = n - i;
if(1ll * a * b == sum) {
found = 1;
break;
}
}

int nn = 0;

for(int i = 0; i <= n; i++){
for(int it = 0; it < num[i]; it++){
c[++nn] = i;
pos[i] = nn;
}
}

for(int i = 0; i <= n + 1; i++){
nxt[i] = i + 1;
prv[i] = i - 1;
}

assert(found);
for(int i = n; i > 0; i--){
int mx = c[prv[n + 1]];
if(a >= b){
if(mx == a){
s[i] = 'b';
del(a);
b--;
}
else{
s[i] = 'a';
del(b);
a--;
}
}
else{
if(mx == b){
s[i] = 'a';
del(b);
a--;
}
else{
s[i] = 'b';
del(a);
b--;
}
}
}
for(int i = 1; i <= n; i++){
d[i] = cnt[1 - (s[i] - 'a')];
cnt[s[i] - 'a']++;
}
sort(d + 1, d + n + 1);
sort(c + 1, c + n + 1);
for(int i = 1; i <= n; i++){
assert(c[i] == d[i]);
}
printf("%s", s + 1);
}

int main () {
int T = 1;
//scanf("%d", &T);

while(T--){
solve();
}

return 0;
}```