2. I10n

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <vector>
#include <stack>
#include <set>
#include <algorithm>    // std::sort
#include <queue>

using namespace std;

struct abbrItem {
    string origin;              // исходная строчка
    string abbr;                // сокращенная
    int index;                  // индекс элемента
    int possible_len;           // макс.возможная длину префикса для сокращения
    bool completed;             // отмечает, завершена ли обработка строки
    bool marked;                // если true, запись отмечена, как конфликтная, и направлена в stack conflicts
};

class Solution {
private:
    queue <int> conflicts;                      // очередь для урегулирования конфликтов
    vector <abbrItem> out;
    map <string, int> abbrmap;                  // карта сокращений, второй параметр -- индекс в out
    int iteration;                              // текущая итерация по формированию сокращений
    void inputStrings(vector <string> &s);
    string getAbbr(string s, int l);
    void resolveConflicts();
    void genAbbr(int i);                        // генерация сокращения
public:
    void Input();
    void Run();
    void Print();
};

void Solution::Input()
{
    string one;
    vector <string> s;
    int n;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> one;
        s.push_back( one ); // запоминаем исходную строчку в векторе
    }
    inputStrings(s);
}

void Solution::Print()
{
    for(auto x : out) {
        cout << x.abbr << endl;
    }
}

string Solution::getAbbr(string s, int l)
{
    string x;
    int len = s.length(), n;

    if(l <= 0 || l*2 >= len) {
        x = s;
    } else {
        n = len - l*2;
        x = s.substr(0,l) + to_string(n) + s.substr(l+n,l);
    }
    return x;
}

void Solution::resolveConflicts()
{
    int index;
    vector<int> v;

    while (conflicts.empty() == false) {
        iteration += 1;
        abbrmap.clear();
        // переписываем conflicts в v
        // одновременно снимаем метку marked
        while (conflicts.empty() == false) {
            index = conflicts.front();
            v.push_back(index);
            conflicts.pop();
            out[index].marked = false;
        }
        // теперь conflicts -- пустой
        // проходим по вектору, для каждого индекса генерим новое сокращение
        for(auto i : v) {
            genAbbr(i);
        }
    }
}

void Solution::genAbbr(int i)
{
    string s;
    map <string, int>::iterator it;
    abbrItem item;

    if(iteration > out[i].possible_len) {
        // сокращение невозможно
        out[i].abbr = out[i].origin;
    } else {
        // сокращение возможно
        s = getAbbr(out[i].origin, iteration);
        out[i].abbr = s;
        if ((it = abbrmap.find(s)) == abbrmap.end()) {
            // сокращения нет в карте, добавляем
            abbrmap[s] = i;
        } else {
            // конфликт, помечаем, позже будем регулировать
            item = out[ it->second ];
            if(item.marked == false) {
                item.marked = true;
                conflicts.push( item.index );
            }
            out[ it->second ] = item;
            if(out[i].marked == false) {
                out[i].marked = true;
                conflicts.push( i );
            }
        }
    }
}

void Solution::Run()
{
    // проход по массиву, осуществляем сокращения
    // запоминаем сокращения в карте abbrmap
    // если есть конфликты, они отправляются в очередь
    // позже будем регулировать конфликты
    iteration = 1;
    for(int i = 0; i < (int)out.size(); i++) {
        out[i].marked = false;
        genAbbr(i);
    }

    // если есть конфликты, они будут в стеке conflicts
    resolveConflicts();
}

void Solution::inputStrings(vector <string> &s)
{
    abbrItem item;
    int len;
    int i = 0;

    for(auto x : s) {
        item.index = i;
        item.origin = x;
        item.abbr = x;
        len = x.length();
        item.possible_len = len < 3 ? 0: len / 2 - 1;
        out.push_back(item);
        i++;
    }
}


int main()
{
    Solution s;

    s.Input();
    s.Run();
    s.Print();

    return 0;
}