Untitled

mail@pastecode.io avatar
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;
}