Submission #175231

---

Source Code Expand

#pragma warning(disable:4996)
#include <iostream>
#include <sstream>
#include <fstream>
#include <complex>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <functional>
#include <numeric>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;

#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair

#define loop(i,a,b) for(int i=(a);i<ull(b);++i)
#define rep(i,n) loop(i,0,n)
#define iter(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define riter(i,c) for(auto i=(c).rbegin(); i!=(c).rend(); ++i)

const double eps = 1e-10;
const double pi = acos(-1.0);
const double inf = (int)1e8;

namespace std {
    template<typename T>ostream&operator<<(ostream&os, vector<T>const&v){
        iter(it, v) os << *it << (it + 1 == v.end() ? "" : ",");
        return os;
    }
    template<typename T, typename U>ostream&operator<<(ostream&os, const pair<T, U>&p){
        return os << "[" << p.dirst << "," << p.second << "]";
    }
}

#define clr(a,i) memset((a), (i) ,sizeof(a))


bool diff(string const& s, string const& t){
    char c1[256] = {};
    char c2[256] = {};
    int n = s.size();
    rep(i, n){
        c1[s[i]]++;
        c2[t[i]]++;
    }
    int res = 0;
    loop(c, 'a', 'z' + 1){
        res += max(0, c1[c] - c2[c]);
    }
    return res;
}

string solve(string s, int k){
    string init = s;
    int n = s.size();
    rep(i, n){
        string rest = s.substr(i);
        //cout << rest << endl;
        sort(all(rest));
        rep(j, rest.size()){
            int mae = s.find(rest[j], i);
            swap(s[i], s[mae]);
            int d = diff(init.substr(i + 1), s.substr(i + 1));
            if (d < k){
                if (s[i] != init[i]) k--;
                break;
            }
            else{
                swap(s[i], s[mae]);
            }
        }
    }
    return s;
}

int main(){
    int n, k;
    while (cin >> n >> k){
        string s; cin >> s;
        cout << solve(s, k) << endl;
    }
}

Submission Info

Judge Result