Submission #175248
Source Code Expand
#include <cstdio>
#include <vector>
#include <cstring>
#include <functional>
#include <algorithm>
#include <math.h>
#include <bitset>
#include <set>
#include <queue>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <complex>
#include <numeric>
#include <map>
#include <time.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef pair<pii,pii> ppp;
typedef pair<ll,ll> pll;
typedef pair<double,int> pdi;
typedef pair<double,double> pdd;
typedef vector<double> vec;
typedef vector<vec> mat;
#define rep(i,n) for (int (i) = 0; (i) < (n); (i)++)
#define repn(i,a,n) for (int (i) = (a); (i) < (n); (i)++)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back
#define SORT(x) sort((x).begin(),(x).end())
#define SORTN(x,n) sort((x),(x)+(n))
#define ERASE(x) (x).erase(unique((x).begin(),(x).end()),(x).end())
#define COUNT(x,c) count((x).begin(),(x).end(),(c))
#define REMOVE(x,c) (x).erase(remove((x).begin(),(x).end(),(c)),(x).end())
#define REVERSE(x) reverse((x).begin(),(x).end())
#define FORIT(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))-(x).begin()
#define lb(x,a) lower_bound((x).begin(),(x).end(),(a))
#define LBN(x,a,n) lower_bound((x),(x)+(n),(a))-(x)
#define lbN(x,a,n) lower_bound((x),(x)+(n),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))-(x).begin()
#define ub(x,a) upper_bound((x).begin(),(x).end(),(a))
#define BS(x,a) binary_search((x).begin(),(x).end(),(a))
#define BS2(x,n,a) binary_search((x),(x)+(n),(a))
#define NB(x) (((x)&~((x)+((x)&-(x))))/((x)&-(x))>>1)|((x)+((x)&-(x)))
#define NP(x) next_permutation((x).begin(),(x).end())
#define MM(x,p) memset((x),(p),sizeof(x))
#define SQ(x) (x)*(x)
#define SC(c1,c2) strcmp(c1,c2)==0
#define mp make_pair
#define INF (1<<29)
#define INFL (1LL<<50)
#define fi first
#define se second
#define MOD 1000000007
#define EPS 1e-8
int N,K;
string a;
int dat[26];
string ans;
bool ok;
void solve(int v,int k)
{
if(ok)return;
if(v==N)
{
if(k<=K)
{
ok=true;
cout<<ans<<endl;
}
return;
}
if(ok)return;
if(k>K)return;
rep(i,26)if(dat[i])
{
dat[i]--;
if(ok)return;
ans[v]='a'+i;
int mk=k+(ans[v]!=a[v]);
repn(j,v+1,N)mk+=(dat[a[j]-'a']==0);
if(mk<=K)solve(v+1,k+(ans[v]!=a[v]));
dat[i]++;
}
}
int main()
{
cin>>N>>K;
cin>>a;
rep(i,N)dat[a[i]-'a']++;
ans=a;
solve(0,0);
}
Submission Info
Submission Time |
|
Task |
C - 辞書式順序ふたたび |
User |
namonakiacc |
Language |
C++ (G++ 4.6.4) |
Score |
0 |
Code Size |
2684 Byte |
Status |
TLE |
Exec Time |
2031 ms |
Memory |
932 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 100 |
Status |
|
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, 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 |
22 ms |
896 KB |
hand_1_1.txt |
AC |
22 ms |
920 KB |
hand_1_2.txt |
AC |
23 ms |
696 KB |
hand_1_3.txt |
AC |
20 ms |
908 KB |
hand_1_4.txt |
AC |
22 ms |
796 KB |
hand_1_5.txt |
AC |
24 ms |
796 KB |
hand_1_6.txt |
AC |
22 ms |
796 KB |
hand_1_7.txt |
AC |
20 ms |
916 KB |
hand_1_8.txt |
AC |
22 ms |
792 KB |
hand_2_0.txt |
AC |
25 ms |
792 KB |
hand_2_1.txt |
AC |
21 ms |
796 KB |
hand_2_10.txt |
AC |
21 ms |
916 KB |
hand_2_2.txt |
AC |
22 ms |
792 KB |
hand_2_3.txt |
AC |
21 ms |
920 KB |
hand_2_4.txt |
AC |
21 ms |
920 KB |
hand_2_5.txt |
AC |
21 ms |
920 KB |
hand_2_6.txt |
AC |
22 ms |
920 KB |
hand_2_7.txt |
AC |
22 ms |
920 KB |
hand_2_8.txt |
AC |
22 ms |
720 KB |
hand_2_9.txt |
AC |
20 ms |
912 KB |
hand_3_2.txt |
AC |
23 ms |
696 KB |
hand_3_3.txt |
AC |
27 ms |
796 KB |
hand_3_4.txt |
AC |
22 ms |
804 KB |
hand_3_5.txt |
AC |
22 ms |
788 KB |
hand_3_6.txt |
AC |
21 ms |
920 KB |
hand_4_2.txt |
AC |
22 ms |
792 KB |
hand_4_3.txt |
AC |
21 ms |
816 KB |
hand_4_4.txt |
AC |
24 ms |
856 KB |
hand_4_5.txt |
AC |
22 ms |
796 KB |
hand_4_6.txt |
AC |
22 ms |
796 KB |
random_1.txt |
AC |
20 ms |
804 KB |
random_10.txt |
TLE |
2030 ms |
812 KB |
random_11.txt |
TLE |
2030 ms |
808 KB |
random_12.txt |
TLE |
2030 ms |
804 KB |
random_13.txt |
TLE |
2031 ms |
800 KB |
random_14.txt |
TLE |
2029 ms |
932 KB |
random_15.txt |
AC |
21 ms |
924 KB |
random_2.txt |
AC |
20 ms |
916 KB |
random_3.txt |
AC |
27 ms |
812 KB |
random_4.txt |
AC |
26 ms |
800 KB |
random_5.txt |
AC |
21 ms |
796 KB |
random_6.txt |
TLE |
2030 ms |
804 KB |
random_7.txt |
AC |
21 ms |
908 KB |
random_8.txt |
AC |
89 ms |
916 KB |
random_9.txt |
TLE |
2029 ms |
804 KB |
sample_1.txt |
AC |
21 ms |
924 KB |
sample_2.txt |
AC |
23 ms |
796 KB |
sample_3.txt |
AC |
21 ms |
796 KB |
sample_4.txt |
AC |
22 ms |
920 KB |
small_1.txt |
AC |
21 ms |
796 KB |
small_2.txt |
AC |
21 ms |
792 KB |
small_3.txt |
AC |
22 ms |
796 KB |
small_4.txt |
AC |
22 ms |
916 KB |
small_5.txt |
AC |
21 ms |
924 KB |
small_6.txt |
AC |
23 ms |
784 KB |
small_7.txt |
AC |
22 ms |
920 KB |
small_8.txt |
AC |
20 ms |
788 KB |
small_9.txt |
AC |
24 ms |
796 KB |