Submission #1674740
Source Code Expand
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <utility>
#include <memory>
#include <functional>
#include <deque>
#include <cctype>
#include <ctime>
#include <numeric>
#include <list>
#include <iomanip>
#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <forward_list>
#define cauto const auto&
#else
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll;
typedef vector<vector<long long> > vvll;
#define VV(T) vector<vector< T > >
template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
v.assign(a, vector<T>(b, t));
}
template <class F, class T>
void convert(const F &f, T &t){
stringstream ss;
ss << f;
ss >> t;
}
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _rep(i,n) _rep2((i),0,(n))
#define _rep2(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define fi first
#define se second
#define mkp make_pair
#define DEBUG
#ifdef DEBUG
#define dump(x) cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x)
#define debug(x)
#endif
#define MOD 1000000007LL
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)
int dp[4010][2010];
template<class T>
struct RollingHash {
static const int NN = 2; // the number of hash table
T base[NN] = {1009, 1007};
T PMOD[NN] = {1000000007, 1000000009};
vector<T> hash[NN];
vector<T> mypow[NN];
int sz;
void init(string s) {
sz = s.size();
for(int i = 0; i < NN; i++) {
hash[i].assign(sz + 1, 0);
mypow[i].assign(sz + 1, 0);
mypow[i][0] = 1;
}
for(int i = 0; i < NN; i++) {
for(int j = 0; j < sz; j++) {
hash[i][j + 1] = (hash[i][j] * base[i] + s[j]) % PMOD[i];
mypow[i][j + 1] = mypow[i][j] * base[i] % PMOD[i];
}
}
}
RollingHash() {
}
// hash[t] value of s[l..r]
T get(int l, int r, int t) {
T ret = (hash[t][r + 1] - hash[t][l] * mypow[t][r - l + 1] % PMOD[t] + PMOD[t]) % PMOD[t];
return ret;
}
// compare s[a..b] and s[c..d] O(1)
bool comp(int a, int b, int c, int d) {
if(a < 0 || sz <= b || c < 0 || sz <= d) return false;
for(int i = 0; i < NN; i++) {
if(get(a, b, i) != get(c, d, i)) return false;
}
return true;
}
// longest common extension s[l..LCE(l,r)] == s[r..LCE(l,r)] && s[l..LCE(l,r)+1] != s[r..LCE(l,r)+1]
int LCE(int l,int r){
// cout<<l<<" "<<r<<endl;
if(l>r) swap(l,r);
// tie(l,r)=minmax(l,r);
// cout<<l<<" "<<r<<endl;
// if(l==5&&r==3){
// cout<<"hoge"<<endl;
// cout<<"ll "<<ll<<endl;
// }
if(l==r) return sz-r+1;
int ll = 0;
int rr = sz;
while(rr-ll>1){
int mid = (ll+rr)>>1;
if(comp(l,l+mid-1,r,r+mid-1)) ll=mid;
else rr=mid;
}
return ll;
}
};
RollingHash<ll> rh;
int compare(int x, int y, int n, string &s){
if(x==-1) return 1;
if(rh.comp(x, x+n-1, y, y+n-1)){
return 0;
}
// assert(x<n&&y<n);
int len = rh.LCE(x, y);
// if(x==5&&y==3){
// cout<<"len "<<len<<endl;
// cout<<"aa "<<s[x]<<" "<<s[y]<<endl;
// }
if(s[x+len]<s[y+len]) return -1;
return 1;
}
int compare2(int x, int y, int n, string &s){
rep(i,n){
if(s[x+i]!=s[y+i]){
if(s[x+i]<s[y+i]) return 1;
else return 0;
}
}
return 0;
}
void mainmain(){
int K;
cin>>K;
string s;
cin>>s;
if(K==0){
cout<<s<<endl;
return;
}
K++;
int n = s.size();
int m = n/K;
int a = n%K;
// cout<<m<<" "<<a<<endl;
assert(n<=2000);
rh.init(s);
if(a==0){
int ans = 0;
rep(i,n){
int p = i*m;
if(p>=n) break;
if(compare2(ans, p, m, s)==1) ans = p;
}
cout<<s.substr(ans, m)<<endl;
return;
}
rep(i,2*n+1) rep(j,K+1) dp[i][j]=-1;
rep(i,1,n){
if(i*m>=n) break;
dp[i*m+1][1] = (i-1)*m;
// cout<<i*m+1<<" "<<n<<endl;
}
// cout<<dp[n][1]<<endl;
rep(i,n){
// cout<<i<<endl;
rep(j,K){
// cout<<"j "<<j<<endl;
if(dp[i][j]==-1) continue;
if(compare(dp[i+m][j], dp[i][j], m+1, s)==1){
dp[i+m][j] = dp[i][j];
}
int p;
if(compare(dp[i][j], i, m+1, s)==-1) p=i;
else p=dp[i][j];
// if(i==5&&j==1) cout<<"p "<<p<<" "<<dp[i+m+1][j+1]<<endl;
if(compare(dp[i+m+1][j+1], p, m+1, s)==1){
dp[i+m+1][j+1] = p;
}
// if(i==5&&j==1) cout<<"p "<<p<<" "<<dp[i+m+1][j+1]<<endl;
}
}
// cout<<dp[n][a]<<endl;
// cout<<dp[3][1]<<endl;
// cout<<dp[5][1]<<endl;
// cout<<dp[8][2]<<endl;
cout<<s.substr(dp[n][a],m+1)<<endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout<<fixed<<setprecision(20);
mainmain();
}
Submission Info
Submission Time |
|
Task |
B - Takahashi the Magician |
User |
j_gui0121 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
5442 Byte |
Status |
RE |
Exec Time |
104 ms |
Memory |
512 KB |
Judge Result
Set Name |
Sample |
subtask1 |
subtask2 |
All |
Score / Max Score |
0 / 0 |
0 / 200 |
0 / 800 |
0 / 200 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
sample_1.txt, sample_2.txt, sample_3.txt |
subtask1 |
sample_1.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 |
sample_1.txt, sample_2.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_2.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt |
All |
sample_1.txt, sample_2.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, sample_1.txt, sample_2.txt, sample_3.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_2.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_10.txt, subtask_3_11.txt, subtask_3_12.txt, subtask_3_13.txt, subtask_3_14.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt |
Case Name |
Status |
Exec Time |
Memory |
hack_1.txt |
RE |
100 ms |
512 KB |
hack_2.txt |
RE |
104 ms |
256 KB |
hack_3.txt |
RE |
103 ms |
256 KB |
hack_4.txt |
RE |
100 ms |
256 KB |
hack_5.txt |
RE |
98 ms |
256 KB |
sample_1.txt |
RE |
98 ms |
256 KB |
sample_2.txt |
RE |
98 ms |
256 KB |
sample_3.txt |
RE |
97 ms |
256 KB |
subtask_1_1.txt |
WA |
1 ms |
256 KB |
subtask_1_10.txt |
RE |
97 ms |
256 KB |
subtask_1_11.txt |
WA |
1 ms |
384 KB |
subtask_1_12.txt |
RE |
98 ms |
256 KB |
subtask_1_13.txt |
RE |
97 ms |
256 KB |
subtask_1_14.txt |
RE |
98 ms |
256 KB |
subtask_1_15.txt |
WA |
1 ms |
384 KB |
subtask_1_16.txt |
WA |
1 ms |
384 KB |
subtask_1_17.txt |
WA |
1 ms |
384 KB |
subtask_1_18.txt |
WA |
1 ms |
384 KB |
subtask_1_19.txt |
RE |
97 ms |
256 KB |
subtask_1_2.txt |
WA |
1 ms |
256 KB |
subtask_1_20.txt |
RE |
98 ms |
256 KB |
subtask_1_3.txt |
WA |
1 ms |
256 KB |
subtask_1_4.txt |
WA |
1 ms |
256 KB |
subtask_1_5.txt |
WA |
1 ms |
256 KB |
subtask_1_6.txt |
WA |
1 ms |
256 KB |
subtask_1_7.txt |
WA |
1 ms |
256 KB |
subtask_1_8.txt |
WA |
1 ms |
384 KB |
subtask_1_9.txt |
WA |
1 ms |
256 KB |
subtask_2_1.txt |
WA |
1 ms |
256 KB |
subtask_2_10.txt |
WA |
1 ms |
256 KB |
subtask_2_11.txt |
WA |
1 ms |
384 KB |
subtask_2_12.txt |
WA |
1 ms |
384 KB |
subtask_2_13.txt |
WA |
1 ms |
384 KB |
subtask_2_14.txt |
WA |
1 ms |
384 KB |
subtask_2_15.txt |
RE |
99 ms |
256 KB |
subtask_2_16.txt |
WA |
1 ms |
384 KB |
subtask_2_17.txt |
WA |
1 ms |
384 KB |
subtask_2_18.txt |
WA |
1 ms |
384 KB |
subtask_2_19.txt |
RE |
99 ms |
256 KB |
subtask_2_2.txt |
WA |
1 ms |
384 KB |
subtask_2_20.txt |
WA |
1 ms |
256 KB |
subtask_2_21.txt |
WA |
1 ms |
256 KB |
subtask_2_22.txt |
WA |
1 ms |
256 KB |
subtask_2_23.txt |
WA |
1 ms |
256 KB |
subtask_2_24.txt |
WA |
1 ms |
256 KB |
subtask_2_25.txt |
RE |
100 ms |
256 KB |
subtask_2_26.txt |
WA |
1 ms |
256 KB |
subtask_2_27.txt |
WA |
1 ms |
256 KB |
subtask_2_3.txt |
WA |
1 ms |
384 KB |
subtask_2_4.txt |
WA |
1 ms |
256 KB |
subtask_2_5.txt |
WA |
1 ms |
384 KB |
subtask_2_6.txt |
WA |
1 ms |
384 KB |
subtask_2_7.txt |
WA |
1 ms |
256 KB |
subtask_2_8.txt |
WA |
1 ms |
256 KB |
subtask_2_9.txt |
WA |
1 ms |
256 KB |
subtask_3_1.txt |
WA |
1 ms |
256 KB |
subtask_3_10.txt |
WA |
1 ms |
384 KB |
subtask_3_11.txt |
WA |
1 ms |
384 KB |
subtask_3_12.txt |
WA |
1 ms |
384 KB |
subtask_3_13.txt |
RE |
102 ms |
256 KB |
subtask_3_14.txt |
RE |
101 ms |
256 KB |
subtask_3_2.txt |
WA |
1 ms |
256 KB |
subtask_3_3.txt |
WA |
1 ms |
384 KB |
subtask_3_4.txt |
WA |
1 ms |
384 KB |
subtask_3_5.txt |
WA |
1 ms |
384 KB |
subtask_3_6.txt |
WA |
1 ms |
384 KB |
subtask_3_7.txt |
WA |
1 ms |
384 KB |
subtask_3_8.txt |
WA |
1 ms |
384 KB |
subtask_3_9.txt |
WA |
1 ms |
384 KB |