Submission #996560

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

string s;
bool used[100001];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int k;
	cin>>k>>s;
	int n = int(s.length());
	int d = (n/(k+1)); int u = d + 1;
	int rem = n%(k+1); //rem times of u
	//cerr<<n<<'\n';
	if(rem == 0)
	{
		string ans;
		for(int j = 0; j < d; j++)
		{
			int tmp = 1;
			for(int i = 0; i < n; i += d)
			{
				if(used[i]) continue;
				if(s[i+j]-'0'>tmp)
				{
					tmp=s[i+j]-'0';
				}
			}
			for(int i = 0; i < n; i += d)
			{
				if(used[i]) continue;
				if(s[i+j]-'0'<tmp)
				{
					used[i]=true;
				}
			}
			ans+=char(tmp+'0');
		}
		cout<<ans<<'\n';
		return 0;
	}
	string ans;
	for(int i = 0; i < u; i++) //BS each digit
	{
		int lo = 1; int hi = 9;
		int an = 0;
		while(lo<=hi)
		{
			int mid = (lo+hi)>>1;
			int j = 0; int cnt = rem;
			//cerr<<cnt<<' '<<u<<'\n';
			while(cnt>0&&j<n)
			{
				//cerr<<j<<' '<<cnt<<' '<<mid<<'\n';
				if(j+u>n) break;
				bool pos = true;
				for(int k = j; k < j + u; k++)
				{
					if(k-j>i)
					{
						break;
					}
					else if(k-j==i)
					{
						if(s[k]-'0'<=mid)
						{
							break;
						}
						else
						{
							pos=false;
							break;
						}
					}
					else
					{
						if(s[k]>ans[k-j])
						{
							pos=false;
							break;
						}
						else if(s[k]<ans[k-j])
						{
							break;
						}
					}
				}
				if(pos)
				{
					cnt--;
					j+=u;
				}
				else
				{
					j+=d;
				}
			}
			//cerr<<i<<' '<<mid<<' '<<cnt<<'\n';
			if(cnt==0)
			{
				an=mid;
				hi=mid-1;
			}
			else
			{
				lo=mid+1;
			}
		}
		ans += char(an+'0');
	}
	cout<<ans<<'\n';
}

Submission Info

Judge Result