fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
  5. using pii = pair<int, int>;
  6.  
  7. struct Element {
  8.     int req_R;    // Ceil(freq / alloc)
  9.     int char_idx; // 0 to 25
  10.     int alloc;    // Copies assigned
  11.     int freq;     // Original frequency
  12.  
  13.     bool operator<(const Element& other) const {
  14.         if (req_R != other.req_R) return req_R < other.req_R;
  15.         return char_idx > other.char_idx;
  16.     }
  17. };
  18.  
  19. void solve() {
  20.     int k;
  21.     string s;
  22.     if (!(cin >> k >> s)) return;
  23.  
  24.     vector<int> freq(26, 0);
  25.     int distinct_cnt = 0;
  26.     int first_char = -1;
  27.  
  28.     for (char c : s) {
  29.         if (freq[c - 'a'] == 0) distinct_cnt++;
  30.         freq[c - 'a']++;
  31.     }
  32.  
  33.     if (k < distinct_cnt) {
  34.         cout << "-1\n";
  35.         return;
  36.     }
  37.  
  38.     for (int i = 0; i < 26; i++) {
  39.         if (freq[i] > 0) {
  40.             first_char = i;
  41.             break;
  42.         }
  43.     }
  44.  
  45.     priority_queue<Element> pq;
  46.     int used_slots = 0;
  47.  
  48.     for (int i = 0; i < 26; i++) {
  49.         if (freq[i] > 0) {
  50.             int init_alloc = 1;
  51.             int req_R = (freq[i] + init_alloc - 1) / init_alloc;
  52.             pq.push({req_R, i, init_alloc, freq[i]});
  53.             used_slots++;
  54.         }
  55.     }
  56.  
  57.     while (used_slots < k) {
  58.         Element top = pq.top();
  59.  
  60.         int new_R = (top.freq + (top.alloc + 1) - 1) / (top.alloc + 1);
  61.  
  62.         if (new_R == top.req_R) {
  63.             break; // Stop redistributing; assign remaining slots to smallest char
  64.         }
  65.  
  66.         pq.pop();
  67.         top.alloc++;
  68.         top.req_R = new_R;
  69.         pq.push(top);
  70.  
  71.         used_slots++;
  72.     }
  73.  
  74.     vector<int> final_alloc(26, 0);
  75.     while (!pq.empty()) {
  76.         auto el = pq.top();
  77.         pq.pop();
  78.         final_alloc[el.char_idx] = el.alloc;
  79.     }
  80.  
  81.     int extra = k - used_slots;
  82.     if (extra > 0 && first_char != -1) {
  83.         final_alloc[first_char] += extra;
  84.     }
  85.  
  86.     string ans = "";
  87.     for (int i = 0; i < 26; i++) {
  88.         if (final_alloc[i] > 0) {
  89.             ans.append(final_alloc[i], (char)('a' + i));
  90.         }
  91.     }
  92.  
  93.     cout << ans << "\n";
  94. }
  95.  
  96. int main() {
  97.     fastio;
  98.     int t = 1;
  99.     // cin >> t; // Uncomment if problem has multiple test cases
  100.     while (t--) {
  101.         solve();
  102.     }
  103.     return 0;
  104. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
7 abbbbccdd
stdout
copy 
aaabbcd
https://ideone.com/otbC11
language:
C++ (gcc 8.3)
created:
23 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!