fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fast ios::sync_with_stdio(false); cin.tie(nullptr);
  5. #define ll long long
  6. #define endl '\n'
  7. #define all(v) (v).begin(), (v).end()
  8. #define rall(v) (v).rbegin(), (v).rend()
  9.  
  10. const int oo = 1e9;
  11. const ll INF = 1e18;
  12.  
  13. void solve(){
  14.     int n; cin >> n;
  15.     vector<int>arr(n);
  16.     for(int i=0 ; i<n ; i++) cin >> arr[i];
  17.     vector<int> s = arr;
  18.     sort(all(s));
  19.     map<ll , ll>a , b , c;
  20.     map<ll , ll>m_a , m_b , m_c ;
  21.     int ord = 0;
  22.     for(int i=0 ; i<n ; i++){
  23.         if(ord==0){
  24.             a[s[i]]++;
  25.             m_a[s[i]]++;
  26.             ord = 1;
  27.         }
  28.         else if(ord==1){
  29.             b[s[i]]++;
  30.             m_b[s[i]]++;
  31.             ord = 2 ;
  32.         }
  33.         else{
  34.             c[s[i]]++;
  35.             m_c[s[i]]++;
  36.             ord = 0;
  37.         }
  38.     }
  39.     ll mex_a;
  40.     for(int i=0 ; i<n ; i++){
  41.         if(!m_a[i]){
  42.             mex_a = i;
  43.             break;
  44.         }
  45.     }
  46.     ll mex_b;
  47.     for(int i=0 ; i<n ; i++){
  48.         if(!m_b[i]){
  49.             mex_b = i;
  50.             break;
  51.         }
  52.     }
  53.     ll mex_c;
  54.     for(int i=0 ; i<n ; i++){
  55.         if(!m_c[i]){
  56.             mex_c = i;
  57.             break;
  58.         }
  59.     }
  60.  
  61.     if((mex_a+mex_b+mex_c) < 2*max({mex_a , mex_b , mex_c})){
  62.         cout<<"NO\n";
  63.         return;
  64.     }
  65.     else {
  66.         cout<<"YES\n";
  67.         for(auto &i : arr){
  68.             if(a[i]){
  69.                 cout<<"A";
  70.                 a[i]=0;
  71.             }
  72.             else if(b[i]){
  73.                 cout<<"B";
  74.                 b[i]=0;
  75.             }
  76.             else{
  77.                 cout<<"C";
  78.                 c[i]=0;
  79.             }
  80.         }
  81.     }
  82.     cout<<"\n";
  83. }
  84.  
  85. int main()
  86. {
  87.     fast
  88.  
  89.     int t = 1;
  90.     cin >> t;
  91.  
  92.     while (t--)
  93.         solve();
  94.  
  95.     return 0;
  96. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
https://ideone.com/TpKQ7J
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!