fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5. #include <ext/pb_ds/assoc_container.hpp>
  6.  
  7. using namespace __gnu_pbds;
  8. // X.find_by_order(k) return kth element. 0 indexed.
  9. // X.order_of_key(k) returns count of elements strictly less than k.
  10. template<class T> using ordered_set = tree<T, null_type, greater<T>,rb_tree_tag, tree_order_statistics_node_update>;
  11. template<class T> using ordered_multi_set = tree<T, null_type, greater_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  12. //typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
  13. //typedef tree<pair<long long,char>,null_type,greater<pair<long long,char>>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
  14. #define ll long long
  15. void Erase(ordered_multi_set<pair<ll,char>> &s,pair<ll,char>val) {
  16.     ll rank = s.order_of_key(val);
  17.     auto it = s.find_by_order(rank);
  18.     s.erase(it);
  19. }
  20.  
  21. signed main() {
  22.     string s;
  23.     cin>>s;
  24.     ll n=s.size();
  25.     map<char,ll>mp;
  26.     for (auto i:s)mp[i]++;
  27.     ll ma=0;
  28.     for (auto [x,y]:mp) {
  29.         ma=max(ma,y);
  30.     }
  31.     if (ma>n-ma+1) {
  32.         cout<<"NO";
  33.         return 0;
  34.     }
  35.     priority_queue<pair<ll,char>>q;
  36.     ordered_multi_set<pair<ll,char>>st;
  37.     for (auto [x,y]:mp) {
  38.        // q.push({y,x});
  39.         st.insert({y,x});
  40.     }
  41.     string ans="";
  42.     while (!st.empty()) {
  43.         auto [x,y]=*st.begin();
  44.         if (ans.empty()) {
  45.             ans.push_back(y);
  46.             Erase(st,{x,y});
  47.             x--;
  48.             if (x!=0) {
  49.                 st.insert({x,y});
  50.             }
  51.         }else {
  52.             if (ans[(int)ans.size()-1]!=y) {
  53.                 ans.push_back(y);
  54.                 Erase(st,{x,y});
  55.                 x--;
  56.                 if (x!=0) {
  57.                 st.insert({x,y});
  58.                 }
  59.             }else {
  60.                 Erase(st,{x,y});
  61.                 auto [c,d]=*st.begin();
  62.                 ans.push_back(d);
  63.                 Erase(st,{c,d});
  64.                 c--;
  65.                 if (c!=0) {
  66.                     st.insert({c,d});
  67.                 }
  68.                 st.insert({x,y});
  69.             }
  70.         }
  71.     }
  72.     cout<<"YES\n";
  73.     cout<<ans<<"\n";
  74.  
  75.  
  76.  
  77.     return 0;
  78. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
aaaabcd
stdout
copy 
YES
adacaba
https://ideone.com/SRAnW1
language:
C++ (gcc 8.3)
created:
4 hours 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!