Submission #2517201

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <utility>
#include <string>
#include <vector>
using namespace std;

int k;

// 左が遅いと正
int compareChar(const char lhs[], const char rhs[], int nl, int nr)
{
    // 空文字列は最後
    if (nl == 0 && nr > 0) return 1;
    if (nr == 0 && nl > 0) return -1;
    if (nl == 0 && nr == 0) return 0;

    int n = min(nl, nr);
    for (int i=0; i<n; i++)
    {
        if (lhs[i] > rhs[i]) return 1;
        if (lhs[i] < rhs[i]) return -1;
    }
    if (nl > nr) return 1;
    if (nl < nr) return -1;
    return 0;
}

int main()
{
    string line;
    cin >> line >> k;
    int len = line.size();
    const char* str = line.c_str();

    std::vector<pair<int, int> > best5(k, make_pair(0, 0));

    int atama = -1;

    while (true)
    {
        int min_ = 1000000;
        for (int i=0; i<len; i++)
        {
            if ((int)str[i] < min_ && (int)str[i] > atama) min_ = str[i];
        }
        if (min_ == 1000000) break;
        atama = min_;

        std::vector<int> min_list;
        for (int i=0; i<len; i++)
        {
            if (str[i] == atama) min_list.push_back(i);
        }

        for (auto i : min_list)
        {
            for (int j=1; j<=5; j++)
            {
                if (i+j>len) break;
                for (int l=0; l<k; l++)
                {
                    int res = compareChar(str + best5[l].first, str + i, best5[l].second, j);
                    if (res > 0)
                    {
                        best5.insert(best5.begin() + l, make_pair(i, j));
                        best5.pop_back();
                        break;
                    }
                    if (res == 0) break;
                    if (res < 0) continue;
                }
            }
        }
        if (best5[k-1].second > 0)
        {
            for (int i = best5[k-1].first; i<best5[k-1].first+best5[k-1].second; i++)
                cout << str[i];
            cout << "\n";
            return 0;
        }
    }

    return 0;
}

Submission Info

Judge Result