Submission #40069207

---

Source Code Expand

#include<bits/stdc++.h>
#define N 2001001
#define MAX 2001
using namespace std;
typedef long long ll;
typedef long double db;
const int mod=1e9+21,mod2=1e9+9;
const ll inf=1e18;
inline void read(ll &ret)
{
    ret=0;char c=getchar();bool pd=false;
    while(!isdigit(c)){pd|=c=='-';c=getchar();}
    while(isdigit(c)){ret=(ret<<1)+(ret<<3)+(c&15);c=getchar();}
    ret=pd?-ret:ret;
    return;
}
ll n,k,pos[N];
bool suf[2005][10005];
vector<char>s[N];
char ss[N];
char now[N];
bool f[2005][10005];
ll bas[N],base=13331;
ll thas[N];
vector<ll>has[N];
inline ll gethash(ll i,ll l,ll r)
{
	return (has[i][r]-has[i][l-1]*bas[r-l+1]%mod+mod)%mod;
}
ll st[N],head;
signed main()
{
	bas[0]=1;
	for(int i=1;i<N;i++)
		bas[i]=bas[i-1]*base%mod;
	read(n);
	read(k);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",ss+1);
		ll len=strlen(ss+1);
		s[i].resize(len+1);
		has[i].resize(len+1);
		has[i][0]=0;
		for(int j=1;j<=len;j++)
			s[i][j]=ss[j],has[i][j]=(has[i][j-1]*base+ss[j])%mod;
	}
	suf[n+1][0]=1;
	for(int i=n;i;i--)
	{
		ll lenth=s[i].size()-1;
		for(int j=0;j<=k;j++)
		{
			suf[i][j]=suf[i+1][j];
			if(j>=lenth)
				suf[i][j]|=suf[i+1][j-lenth];
		}
	}
	f[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		ll lenth=s[i].size()-1;
		pos[0]=0;
		has[0].resize(k+1);
		has[0][0]=0;
		for(int j=1;j<=k;j++)
			has[0][j]=(has[0][j-1]*base+now[j])%mod;
		for(int j=1;j<=k;j++)
		{
			pos[j]=-1;
			if(!suf[i+1][k-j])
				continue;
			if(f[i-1][j])
				pos[j]=j;
		//	cerr<<j<<" "<<pos[j]<<endl;
			if(j>=lenth&&f[i-1][j-lenth])
			{
				if(pos[j]==-1)
					pos[j]=j-lenth;
				else
				{
					ll l=1,r=lenth,mid,res=0;
					while(l<=r)
					{
						mid=l+r>>1;
						if(gethash(i,1,mid)==gethash(0,j-lenth+1,j-lenth+mid))
							res=mid,l=mid+1;
						else
							r=mid-1;
					}
			//		cerr<<"? "<<mid<<endl;
					if(res==lenth||now[j-lenth+res+1]>=s[i][res+1])
						pos[j]=j-lenth;
				}
			}
	//	cout<<i<<' '<<j<<" "<<pos[j]<<endl;
		}
		head=0;
		for(int j=1;j<=k;j++)
		{
			if(~pos[j])
			{
				if(!head)
					st[++head]=j;
				else
				{
					while(head)
					{
						ll len=st[head];
						ll l=1,r=len,mid,res=0;
				//		cout<<"? "<<j<<' '<<len<<endl;
						while(l<=r)
						{
							mid=l+r>>1;
							ll res1,res2;
							if(pos[j]==j)
								res1=gethash(0,1,mid);
							else
							{
								if(mid<=j-lenth)
									res1=gethash(0,1,mid);
								else
									res1=(gethash(0,1,j-lenth)*bas[mid-(j-lenth)]+gethash(i,1,mid-(j-lenth)))%mod;
							}
							if(pos[len]==len)
								res2=gethash(0,1,mid);
							else
							{
								if(mid<=len-lenth)
									res2=gethash(0,1,mid);
								else
									res2=(gethash(0,1,len-lenth)*bas[mid-(len-lenth)]+gethash(i,1,mid-(len-lenth)))%mod;
							}
							if(res1==res2)
								l=mid+1,res=mid;
							else
								r=mid-1;
						}
						if(res==len)
						{
							st[++head]=j;
							break;
						}
						else
						{
							ll c1,c2;
							if(pos[j]==j)
								c1=now[res+1];
							else
							{
								if(res+1<=j-lenth)
									c1=now[res+1];
								else
									c1=s[i][res+1-(j-lenth)];
							}
							if(pos[len]==len)
								c2=now[res+1];
							else
							{
								if(res+1<=len-lenth)
									c2=now[res+1];
								else
									c2=s[i][res+1-(len-lenth)];
							}
							if(c1<c2)
								head--;
							else
								break;
						}
					}
					if(!head)
						st[++head]=j;
				}
			}
		}
		ll len=st[head];
		for(int j=len+1;j<=k;j++)
			now[j]=0;
		if(pos[len]==len)
		{
			for(int j=len+1;j<=k;j++)
				now[j]=0;
		}
		else
		{
			for(int j=len-lenth+1;j<=len;j++)
				now[j]=s[i][j-(len-lenth)];
		}
		for(int j=1;j<=head;j++)
			f[i][st[j]]=true;
		f[i][0]=true;
	/*	cout<<i<<endl;
		for(int j=1;j<=k;j++)
			putchar(now[j]);
		putchar('\n');*/
	/*	for(int j=1;j<=head;j++)
			cout<<st[j]<<" ";
		
		cout<<endl;*/
	}
	for(int j=1;j<=k;j++)
		putchar(now[j]);
	exit(0);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:85:12: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   85 |       mid=l+r>>1;
      |           ~^~
./Main.cpp:114:13: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
  114 |        mid=l+r>>1;
      |            ~^~
./Main.cpp:40:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   40 |   scanf("%s",ss+1);
      |   ~~~~~^~~~~~~~~~~

Judge Result