Construction problem of D Xiaohong

Portal ：
D Xiao Hong's construction problem

The question ： Construct a length that does not exceed 2e5 String of , Make it include k individual “red” Subsequence .(k<=1e14)

analysis ： At first, I wanted to get together rreedd This string , Then add the letters . However, the newly added letters have aftereffect and the number of subsequences cannot be added 1, be unable to do sth. .

consider rrrededed This string , Again only again ed Before to add r, Then add... At any position r There will be no aftereffect . If r Yes x individual , So this string has x*(x+1)*x/2 Subsequence , obviously x The length of is pow(1e14,1/3.0) Level , The remaining k The length of x^2 The level of . After that in each ed Add one before r, Will increase i(i+1)/2 Subsequence , And no aftereffect . As if ,- The largest square number is also a function of rapid numerical descent ？ Run fast anyway .

Code ：

#include<bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
	// cout<<pow(1e14,1/3.0)<<endl;
	int k;
	cin>>k;
	int x=0;
	while(1)
	{
		if(x*x*(x+1)/2>k)
		{
			x--;
			break;
		}
		else x++;
	}
	cout<<x<<endl;
	k-=x*x*(x+1)/2;
	for(int i=1;i<=x;i++)
	{
		cout<<"r";
	}
	// int cnt=0;
	for(int i=x;i>=1;i--)
	{
		while(k>=i*(i+1)/2)
		{
			k-=i*(i+1)/2;
			cout<<"r";
			// cnt++;
		}
		cout<<"ed";
	}
	cout<<endl;
	// cout<<cnt<<endl;
}