1051C - Vasya and Multisets - CodeForces Solution

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
 
#include <bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
*/
using namespace std;
#define int long long
#define ll long long
#define ld long double
#define all(container) container.begin(), container.end()
#define allr(container) container.rbegin(), container.rend()
#define SORT(container) sort(all(container))
#define SORTR(container) sort(allr(container))
#define UNIQUE(container) sort(all(container)), x.erase(unique(all(x)), x.end())
#define cnt(s, c) count(all(s), c)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define len(container) (int)(container).size()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define drop(x) cout << #x << endl, exit(0);
template <class T> using pq = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
template <class T> void scan(T &a) { cin >> a; }
void IN() {}
template <class Head, class... Tail> void IN(Head &head, Tail &...tail) {
    scan(head);
    IN(tail...);
}
#define INT(...)\
    int __VA_ARGS__;\
    IN(__VA_ARGS__)
#define LL(...)\
    ll __VA_ARGS__;\
    IN(__VA_ARGS__)
#define STR(...)\
    string __VA_ARGS__;\
    IN(__VA_ARGS__)
#define CHR(...)\
    char __VA_ARGS__;\
    IN(__VA_ARGS__)
#define DBL(...)\
    double __VA_ARGS__;\
    IN(__VA_ARGS__)
#define TEST \
INT(testcases); \
while(testcases--)
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pii>
#define vpll vector<pll>
#define vec(type, name, ...) vector<type> name(__VA_ARGS__)
#define VEC(type, name, size) \
    vector<type> name(size); \
    IN(name)
#define VEC2(type, name1, name2, size) \
    vector<type> name1(size), name2(size); \
    for(int i = 0; i < size; i++) IN(name1[i], name2[i])
#define VEC3(type, name1, name2, name3, size) \
    vector<type> name1(size), name2(size), name3(size); \
    for(int i = 0; i < size; i++) IN(name1[i], name2[i], name3[i])
#define VEC4(type, name1, name2, name3, name4, size) \
    vector<type> name1(size), name2(size), name3(size), name4(size); \
    for(int i = 0; i < size; i++) IN(name1[i], name2[i], name3[i], name4[i]);
#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define VV(type, name, h, w)\
    vector<vector<type>> name(h, vector<type>(w)); \
    IN(name)
#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
    vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))

namespace yesno_impl {
const string YESNO[2] = {"NO", "YES"};
const string YesNo[2] = {"No", "Yes"};
const string yesno[2] = {"no", "yes"};
const string firstsecond[2] = {"second", "first"};
const string FirstSecond[2] = {"Second", "First"};
const string possiblestr[2] = {"impossible", "possible"};
const string Possiblestr[2] = {"Impossible", "Possible"};
void YES(bool t = 1) { cout << YESNO[t] << endl; }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { cout << YesNo[t] << endl; }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { cout << yesno[t] << endl; }
void no(bool t = 1) { yes(!t); }
void first(bool t = 1) { cout << firstsecond[t] << endl; }
void First(bool t = 1) { cout << FirstSecond[t] << endl; }
void possible(bool t = 1) { cout << possiblestr[t] << endl; }
void Possible(bool t = 1) { cout << Possiblestr[t] << endl; }
}; // namespace yesno_impl
using namespace yesno_impl;

#define mt make_tuple
#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define MIN(container) min_element(all(container))
#define MAX(container) max_element(all(container))
#define SUM(container) accumulate(all(container), 0ll)
template<typename T> static constexpr T inf = numeric_limits<T>::max()/2;
const double EPS = 1E-9;
const int INF = 1000000000;
const ll INF64 = (ll) 1E18;
const double PI = 3.1415926535897932384626433832795;
constexpr int MOD = 1e9+7;
constexpr int MOD2 = 998244353;
template <class T>
using min_heap = priority_queue<T,vector<T>,greater<T> >; 
template<typename _Tp>
istream& operator >> (istream& i, vector<_Tp>& v){
  for(_Tp& x : v)
    i >> x;
  return i;
}
template<typename _Tp1, typename _Tp2>
istream& operator >> (istream& i, pair<_Tp1, _Tp2>& v){
  i >> v.ff >> v.ss;
  return i;
}
template<class T>
vector<T>& operator -- (vector<T>& v){
  for(T&x: v) --x;
  return v;
}
template<class T>
vector<T>& operator ++ (vector<T>& v){
  for(T&x: v) ++x;
  return v;
}
template<class T> 
pair<T, T>& operator -- (pair<T, T>& v){
    --v.ff, --v.ss;
    return v;
}
template<class T> 
pair<T, T>& operator ++ (pair<T, T>& v){
    ++v.ff, ++v.ss;
    return v;
}
template <class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); }
template <class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); }
vi iota(int n) {
    vi a(n);
    iota(all(a), 0);
    return a;
}

#ifndef varahamihira_
template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
    for(auto it = begin(v); it != end(v); ++it) {
        if(it == begin(v))
            os << *it;
        else
            os << " " << *it;
    }
    return os;
}
template <class T, class S> ostream &operator<<(ostream &os, const pair<T, S> &p) {
    os << p.first << " " << p.second;
    return os;
}
#endif
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
//order statistic tree
//template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
//cout << s.order_of_key(3) << endl; // the number of elements in s less than 3 (in this case, 0-based index of element 3)
//cout << *s.find_by_order(1) << endl; // 1-st elemt in s (in sorted order, 0-based)
ll mulMod(ll a, ll b, ll c=MOD){ ll res=0, y=a%c; while(b > 0){ if(b&1) res = (res + y) % c; b >>= 1ll; y=(2*y)%c; } return res; }
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p=MOD){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
double squareroot(double x, int precision=5){
  double l=0, r=x, ans;
  while(l <= r){
    double mid = l + (r-l)/(2*1.);
    if(mid * mid < x)
      ans=mid, l=mid+1;
    else if(mid * mid > x)
      r=mid-1;
    else{
      ans=mid;
      break;
    }
    //cout << mid << '\n';
  }
  double increment=0.1;
  for(int i=0; i<precision; ++i){
    while(ans * ans <= x)
      ans += increment;
    ans -= increment;
    increment /= 10;
  }
  return ans;
}
vector<pll> factor(ll x) {
    vector<pll> ans;
    for(ll i = 2; i * i <= x; i++)
        if(x % i == 0) {
            ans.push_back({i, 1});
            while((x /= i) % i == 0) ans.back().second++;
        }
    if(x != 1) ans.push_back({x, 1});
    return ans;
}
template <class T> vector<T> divisor(T x) {
    vector<T> ans;
    for(T i = 1; i * i <= x; i++)
        if(x % i == 0) {
            ans.pb(i);
            if(i * i != x) ans.pb(x / i);
        }
    return ans;
}
//#include "./../debug.cpp"
signed main(){
#ifdef varahamihira_
   freopen("input.txt", "r", stdin);
   freopen("output.txt", "w", stdout);
#endif
  ios::sync_with_stdio(false);
  cin.tie(0);
  INT(n);
  VEC(int, A, n);
  set<int> p[2];

  map<int, int> mpp;
  for(int i=0; i<n ;++i)
    ++mpp[A[i]];

  int pos=0;
  for(auto it: mpp){
    if(it.ss == 1){
      p[pos].insert(it.ff);
      pos ^= 1;
    }
  }

  if(len(p[0]) == len(p[1])){
    string ans = string(n, 'A');

    for(int i=0; i<n; ++i)
      if(p[1].count(A[i]))
        ans[i]='B';

    cout << "YES\n" << ans;
  }
  else{
    assert(len(p[0]) - 1 == len(p[1]));

    string ans(n, 'A');
    for(int i=0; i<n; ++i)
      if(p[1].count(A[i]))
        ans[i]='B';

    int id=-1;
    for(auto it: mpp)
      if(it.ss >= 3){
        id = it.ff;
        break;
      }

    if(id == -1)
      cout << "NO";
    else{
      bool flag=false;
      for(int i=0; i<n && !flag; ++i)
        if(A[i] == id){
          if(!flag){
            flag = true;
            ans[i]='B';
          }
        }

      cout << "YES\n" << ans;
    }
  }
  cout << endl;
  return 0;
}