Submission #4067958


Source Code Expand

#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("YES")
#define p_no() p("NO")

template < typename T >
void vprint(T &V){
	for(auto v : V){
    	cout << v << " ";
	}
	cout << endl;
}

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

const ll mod = 1e9 + 7;
const ll inf = 1e18;

int simple_distance(string s, string t){
    int count = 0;
    FOR(i, 0, s.size()){
        if(s[i]!=t[i]){
            count++;
        }
    }
    return count;
}

// sは動かさず、tは自由に動かした場合の最小距離
// s : abc
// t : ccb 
// 
// return (1, cbc)
pair<int, string> difference(string s, string t){
    map<char, int> mp;
    for(char c : t){
        mp[c]++;
    }

    string u = t;
    FOR(i, 0, s.size()){
        char c = s[i];
        if(mp[c]>0){
            mp[c]--;
            u[i] = c;
        }
        else{
            u[i] = '*';
        }
    }

    // tでまだ使っていない文字
    vector<char> not_yet_used;
    for(auto p : mp){
        char c = p.first;
        int count = p.second;
        FOR(i, 0, count){
            not_yet_used.push_back(c);
        }
    }
    sort(ALL(not_yet_used));

    for(char c : not_yet_used){
        int i = 0;
        while(i!=u.size()){
            if(u[i]=='*'){
                u[i] = c;
                break;
            }else{
                i++;
            }
        }
    }

    int count = 0;
    for(auto p : mp){
        count += p.second;
    }
    return make_pair(count, u);;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N, K;
    cin >> N >> K;

    string s;
    cin >> s;

    string t = s;
    sort(ALL(t));

    vector<string> candidates;

    // i : 前半のカットサイズ
    FOR(i, 0, s.size()+1){
        string s0 = s.substr(0, i);
        string s1 = s.substr(i);

        string t0 = t.substr(0, i);
        string t1 = t.substr(i);

        // 前半の差
        int dist0 = simple_distance(s0, t0);

        // 後半
        int rest_K = K - dist0;
        auto p1 = difference(s1, t1);
        int difference1 = p1.first;
        string u1 = p1.second;

        if(dist0 > K){
            // 実現不可
        }else if(dist0 == K){
            if(difference1==0){
                candidates.push_back(t0+u1);
            } 
        }
        // dist0 < K
        else{
            if(rest_K >= difference1){
                // 後半も収まるなら
                candidates.push_back(t0+u1);
            }
        }    
    }

    sort(ALL(candidates));
    p(candidates[0]);    
    
    return 0;
}

Submission Info

Submission Time
Task C - 辞書式順序ふたたび
User peroon
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3053 Byte
Status WA
Exec Time 3 ms
Memory 256 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 47
WA × 11
Set Name Test Cases
All hand_1_0.txt, hand_1_1.txt, hand_1_2.txt, hand_1_3.txt, hand_1_4.txt, hand_1_5.txt, hand_1_6.txt, hand_1_7.txt, hand_1_8.txt, hand_2_0.txt, hand_2_1.txt, hand_2_10.txt, hand_2_2.txt, hand_2_3.txt, hand_2_4.txt, hand_2_5.txt, hand_2_6.txt, hand_2_7.txt, hand_2_8.txt, hand_2_9.txt, hand_3_2.txt, hand_3_3.txt, hand_3_4.txt, hand_3_5.txt, hand_3_6.txt, hand_4_2.txt, hand_4_3.txt, hand_4_4.txt, hand_4_5.txt, hand_4_6.txt, random_1.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_2.txt, random_3.txt, random_4.txt, random_5.txt, random_6.txt, random_7.txt, random_8.txt, random_9.txt, sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, small_1.txt, small_2.txt, small_3.txt, small_4.txt, small_5.txt, small_6.txt, small_7.txt, small_8.txt, small_9.txt
Case Name Status Exec Time Memory
hand_1_0.txt AC 1 ms 256 KB
hand_1_1.txt AC 1 ms 256 KB
hand_1_2.txt AC 1 ms 256 KB
hand_1_3.txt AC 1 ms 256 KB
hand_1_4.txt AC 1 ms 256 KB
hand_1_5.txt AC 1 ms 256 KB
hand_1_6.txt AC 1 ms 256 KB
hand_1_7.txt AC 1 ms 256 KB
hand_1_8.txt AC 1 ms 256 KB
hand_2_0.txt AC 1 ms 256 KB
hand_2_1.txt AC 1 ms 256 KB
hand_2_10.txt AC 1 ms 256 KB
hand_2_2.txt AC 1 ms 256 KB
hand_2_3.txt AC 1 ms 256 KB
hand_2_4.txt AC 1 ms 256 KB
hand_2_5.txt AC 1 ms 256 KB
hand_2_6.txt AC 1 ms 256 KB
hand_2_7.txt AC 1 ms 256 KB
hand_2_8.txt AC 1 ms 256 KB
hand_2_9.txt AC 1 ms 256 KB
hand_3_2.txt AC 1 ms 256 KB
hand_3_3.txt WA 1 ms 256 KB
hand_3_4.txt AC 1 ms 256 KB
hand_3_5.txt WA 1 ms 256 KB
hand_3_6.txt AC 1 ms 256 KB
hand_4_2.txt AC 1 ms 256 KB
hand_4_3.txt WA 1 ms 256 KB
hand_4_4.txt AC 1 ms 256 KB
hand_4_5.txt WA 1 ms 256 KB
hand_4_6.txt AC 3 ms 256 KB
random_1.txt WA 1 ms 256 KB
random_10.txt AC 2 ms 256 KB
random_11.txt WA 2 ms 256 KB
random_12.txt WA 2 ms 256 KB
random_13.txt WA 2 ms 256 KB
random_14.txt AC 2 ms 256 KB
random_15.txt AC 2 ms 256 KB
random_2.txt AC 1 ms 256 KB
random_3.txt AC 2 ms 256 KB
random_4.txt WA 2 ms 256 KB
random_5.txt AC 2 ms 256 KB
random_6.txt WA 2 ms 256 KB
random_7.txt AC 2 ms 256 KB
random_8.txt AC 2 ms 256 KB
random_9.txt WA 2 ms 256 KB
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
sample_3.txt AC 1 ms 256 KB
sample_4.txt AC 1 ms 256 KB
small_1.txt AC 1 ms 256 KB
small_2.txt AC 1 ms 256 KB
small_3.txt AC 1 ms 256 KB
small_4.txt AC 1 ms 256 KB
small_5.txt AC 1 ms 256 KB
small_6.txt AC 1 ms 256 KB
small_7.txt AC 1 ms 256 KB
small_8.txt AC 1 ms 256 KB
small_9.txt AC 1 ms 256 KB