Source Code
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <class T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using i64 = int64_t;

int indexOfLastChar(const string &s) {
  for (int i = (int)s.size() - 1; i >= 0; --i) {
    if (isalpha(s[i])) {
      return i;
    }
  }
  return -1;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout << boolalpha;
  
  int n;
  cin >> n;
  unordered_set<string> st;
  map<string, indexed_set<string>> mp;
  
  auto makeString = [&](const string &s) -> string {
    int lastCharIndex = indexOfLastChar(s);
    string prefix = s.substr(0, lastCharIndex + 1);
    string suffix = s.substr(lastCharIndex + 1);
    indexed_set<string> &withoutSuffixSet = mp[prefix];
    
    auto can = [&](int mid) -> bool {
      int sum = withoutSuffixSet.order_of_key(suffix + to_string(mid + 1));
      int offset = withoutSuffixSet.order_of_key(suffix + "1");
      sum -= offset;
      return mid > sum;
    };

    int lo = 1, hi = 1e5, best = -1;
    while (lo <= hi) {
      int mid = (lo + hi) / 2;
      if (can(mid)) {
        best = mid;
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }

    assert(best != -1);

    return s + to_string(best);
  };

  auto addString = [&](const string &s) {
    assert(st.find(s) == st.end());
    st.insert(s);
    int lastCharIndex = indexOfLastChar(s);
    mp[s.substr(0, lastCharIndex + 1)].insert(s.substr(lastCharIndex + 1));
  };

  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    if (st.find(s) == st.end()) {
      cout << "ok\n";
    } else {
      s = makeString(s);
      cout << s << '\n';
    }
    addString(s);
  }

  return 0;
}
Copy
Registration System abdulrahman_aj
GNU G++17
1 ms
312 KB
Runtime Error