Submission #1016859

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
int k;
string s;
int l;
vector<string> v;
string vv[111111];

bool ch(string x){
  int p = 0;
  for(int i = 0; i < k+1; i++){

    if(p+l > (int)s.size()) return true;
    if(x >= s.substr(p,l)){
      p += l;
    }else{
      p += l-1;
    }
  }
  return p == (int)s.size();
}

bool u[111111];
bool uv[111111]; 
bool dfs(int x){
  if(x > (int)s.size()) return false;
  if(x == (int)s.size()) return true;
  if(uv[x]) return u[x];
  uv[x] = true;

  bool a = dfs(x+l);
  bool b = dfs(x+l-1);
  u[x] = b;

  return u[x] = a||b;
}

int main(void){
  cin >> k >> s;

  if(k == 0){
    cout << s << endl;
    return 0;
  }

  l = (s.size()+k)/(k+1);

  dfs(0);
  for(int i = 0; i+l-1 < (int)s.size(); i++){
    if(u[i])
      v.push_back(s.substr(i,l));
  }
  sort(v.begin(),v.end());

  /*
  cout << "vs " << v.size() << endl;
  for(int i = 0; i < (int)v.size(); i++)
    cout << v[i] << endl;
  */

  int lb = -1;
  int ub = v.size()-1;
  while(ub-lb > 1){
    int mid = (lb+ub)/2;
    /*
    cout << lb << " " << ub << endl;
    cout << "mid " << v[mid] << endl;
    //*/
    if(ch(v[mid])){
      ub = mid;
    }else{
      lb = mid;
    }
  }
  cout << v[ub] << endl;
}

Submission Info

Judge Result