Submission #998727

---

Source Code Expand

#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PB push_back
#define MP make_pair
#define MOD 1000000007LL
#define endl "\n"
const ll UNDEF = -1;
const ll INF=1e18;
template<typename T> inline bool chkmax(T &aa, T bb) { return aa < bb ? aa = bb, true : false; }
template<typename T> inline bool chkmin(T &aa, T bb) { return aa > bb ? aa = bb, true : false; }
typedef pair<ll,ll> pll;

#ifdef DEBUG
     #define debug(args...)            {dbg,args; cerr<<endl;}
#else
    #define debug(args...)              // Just strip off all debug tokens
#endif

struct debugger
{
    template<typename T> debugger& operator , (const T& v)
    {    
        cerr<<v<<" ";    
        return *this;    
    }
} dbg;
ll k; string s;
bool cmp(pll a, pll b) {
	ll an=a.second-a.first,bn=b.second-b.first;
	if (an<bn) return true;
	if (an>bn) return false;
	for (ll i=0;i<an;i++) {
		if (s[a.first+i]<s[b.first+i]) return true;
		if (s[a.first+i]>s[b.first+i]) return false;
	}
	return false;
}
string go(ll x, ll y) {
	return s.substr(x,y-x);
}
bool leq(pll a, pll b) {
	ll an=a.second-a.first,bn=b.second-b.first;
	if (an<bn) return true;
	if (an>bn) return false;
	for (ll i=0;i<an;i++) {
		//cout<<s[a.first+i]<<s[b.first+i]<<endl;
		if (s[a.first+i]<s[b.first+i]) return true;
		if (s[a.first+i]>s[b.first+i]) return false;
	}
	return true;
}
int main() 
{
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin>>k>>s;
	ll n=s.length();
	assert(leq(MP(0,3),MP(4,7)));
	ll q=max(1LL,n/(k+1));
	vector<pll> v;
	for (ll i=0;i<n;i++) {
		if (i+q<=n) v.PB(MP(i,i+q));
		if (i+q+1<=n) v.PB(MP(i,i+q+1));
	}
	//cout<<q<<endl;
	sort(v.begin(),v.end(),cmp);
	for (ll i=0;i<v.size();i++) {
		ll imid=i;
		//cout<<"i:"<<i<<":"<<go(v[imid].first,v[imid].second)<<endl;
	}
	ll imin=0,imax=v.size();
	while(imin<imax) {
		ll imid=(imin+imax)/2;
		//cout<<"imid"<<go(v[imid].first,v[imid].second)<<endl;
		ll x=0;
		bool ok=true;
		for (ll i=0;i<k+1;i++) {
			//cout<<go(x,min(x+q+1,n))<<"<=ISA?"<<go(v[imid].first,v[imid].second);
			if (leq(MP(x,min(x+q+1,n)),v[imid])) {
				//cout<<go(x,min(x+q+1,n))<<"<=A"<<go(v[imid].first,v[imid].second);
				x=min(x+q+1,n);
			}
			else if (leq(MP(x,min(x+q,n)),v[imid])) {
				//cout<<go(x,min(x+q,n))<<"<=B"<<go(v[imid].first,v[imid].second);
				x=min(x+q,n);
			}
			else {
				ok=false; break;
			}
			//cout<<x<<endl;
		}
		if (ok&&x==n) {
			imax=imid;
		}
		else {
			imin=imid+1;
		}
	}
	{
		ll x=v[imin].first,y=v[imin].second;
		cout<<s.substr(x,y-x)<<endl;
	}
}

Submission Info

Judge Result