Submission #4043890


Source Code Expand

//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

bool debug = false;
ll nl, nm;

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

  int n, k;
  string s;

  cin >> n >> k;
  cin >> s;

  vector<char> v;
  REP(i, s.size()) v.push_back(s[i]);
  sort(v.begin(),v.end());  

  int cnt = 0;
  REP(i, v.size()){
    if(v[i] != s[i]) cnt++;
  }
  if(k > cnt) {REP(i, v.size()) {cout << v[i];} cout << endl; return 0;}

  int vitr = 0;  
  //REP(i, s.size()){
  while(k>0){
    int opt = s.find(v[vitr]);    
    int cur = s.find(s[vitr]);
    if(debug) cout << "s: " << s << " opt: " << opt << " cur: " << cur << " k: " << k << endl;
    if(opt != cur) {
      swap(s[opt], s[cur]);
      k--;
    }
    if(s[opt] != v[cur]) k--;      
    
    vitr++;
  }
  
  cout << s << endl;
  
  /*
  string l="", r="";
  REP(i, k) l += v[i];
  FOR(i, k, s.size()) r += v[i];
  */
  
  /*
  int cnt = k;
  REP(j, l.size()){
    if(l[j] != s[j]){
      //swap(l.find(l[j]), l.find(s[j]));
      cout << l.find(l[j]) << " " << l.find(s[j]) << endl;
      cnt-=2;
    }
    if(cnt == 0) break;
  }
  cout << l << r << endl;
  */
  
  return 0;
}

Submission Info

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

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 19
WA × 39
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 WA 1 ms 256 KB
hand_1_2.txt WA 1 ms 256 KB
hand_1_3.txt WA 1 ms 256 KB
hand_1_4.txt WA 1 ms 256 KB
hand_1_5.txt WA 1 ms 256 KB
hand_1_6.txt WA 1 ms 256 KB
hand_1_7.txt WA 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 WA 1 ms 256 KB
hand_2_10.txt AC 1 ms 256 KB
hand_2_2.txt WA 1 ms 256 KB
hand_2_3.txt WA 1 ms 256 KB
hand_2_4.txt WA 1 ms 256 KB
hand_2_5.txt WA 1 ms 256 KB
hand_2_6.txt WA 1 ms 256 KB
hand_2_7.txt WA 1 ms 256 KB
hand_2_8.txt WA 1 ms 256 KB
hand_2_9.txt AC 1 ms 256 KB
hand_3_2.txt WA 1 ms 256 KB
hand_3_3.txt WA 1 ms 256 KB
hand_3_4.txt WA 1 ms 256 KB
hand_3_5.txt WA 1 ms 256 KB
hand_3_6.txt WA 1 ms 256 KB
hand_4_2.txt WA 1 ms 256 KB
hand_4_3.txt WA 1 ms 256 KB
hand_4_4.txt WA 1 ms 256 KB
hand_4_5.txt WA 1 ms 256 KB
hand_4_6.txt WA 1 ms 256 KB
random_1.txt WA 1 ms 256 KB
random_10.txt WA 1 ms 256 KB
random_11.txt WA 1 ms 256 KB
random_12.txt WA 1 ms 256 KB
random_13.txt WA 1 ms 256 KB
random_14.txt WA 1 ms 256 KB
random_15.txt AC 1 ms 256 KB
random_2.txt WA 1 ms 256 KB
random_3.txt WA 1 ms 256 KB
random_4.txt WA 1 ms 256 KB
random_5.txt AC 1 ms 256 KB
random_6.txt WA 1 ms 256 KB
random_7.txt AC 1 ms 256 KB
random_8.txt WA 1 ms 256 KB
random_9.txt WA 1 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 WA 1 ms 256 KB
small_5.txt AC 1 ms 256 KB
small_6.txt AC 1 ms 256 KB
small_7.txt WA 1 ms 256 KB
small_8.txt AC 1 ms 256 KB
small_9.txt AC 1 ms 256 KB