Submission #2746086


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int N=5050;
const int M=10050;
char str[N];
int K;

int ch[M][26],step[M],sum[M],val[M],pre[M],root,cnt,last;
void SAM(int inde,int id)
{
	int u=last;last=++cnt;int now=last;
	step[now]=id;val[now]=1;
	while(u&&!ch[u][inde]) ch[u][inde]=now,u=pre[u];
	if(!u) pre[now]=root;
	else 
	{
		int v=ch[u][inde];
		if(step[u]+1==step[v]) pre[now]=v;
		else 
		{
			int av=++cnt;
			step[av]=step[u]+1;
			memcpy(ch[av],ch[v],sizeof(ch[v]));
			pre[av]=pre[v];pre[v]=pre[now]=av;
			while(u&&ch[u][inde]==v) ch[u][inde]=av,u=pre[u];
		}
	}
}
int buc[M],sa[M];
void prepare()
{
	for(int i=1;i<=cnt;i++) buc[step[i]]++;
	for(int i=1;i<=cnt;i++) buc[i]+=buc[i-1];
	for(int i=1;i<=cnt;i++) sa[buc[step[i]]--]=i;
	
	for(int i=cnt;i>=1;i--) 
	{
		int t=sa[i];
		val[pre[t]]=1;
	}
	val[1]=0;
	for(int i=cnt;i>=1;i--) 
	{
		int t=sa[i];
		sum[t]=val[t];
		for(int j=0;j<26;j++) sum[t]+=sum[ch[t][j]];
	}
}
void solve(int now,int k)
{
	if(k<=val[now]) return ;
	k-=val[now];
	for(int i=0;i<26;i++) 
	{
		if(sum[ch[now][i]]<k) k-=sum[ch[now][i]];
		else 
		{
			printf("%c",'a'+i);
			solve(ch[now][i],k);
			return ;
		}
	}
}
int main()
{
	scanf("%s",&str[1]);
	scanf("%d",&K);
	int len=strlen(&str[1]);
	last=root=cnt=1;
	for(int i=1;i<=len;i++) SAM(str[i]-'a',i);
	prepare();
	solve(1,K);
	return 0;
}

Submission Info

Submission Time
Task C - K-th Substring
User Heey
Language C++14 (GCC 5.4.1)
Score 300
Code Size 1409 Byte
Status AC
Exec Time 2 ms
Memory 1024 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:66:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",&str[1]);
                     ^
./Main.cpp:67:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&K);
                ^

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 200 / 200 100 / 100
Status
AC × 3
AC × 11
AC × 19
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt
Subtask 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 2_011.txt, 2_012.txt, 2_013.txt, 2_014.txt, 2_015.txt, 2_016.txt, 2_017.txt, 2_018.txt
Case Name Status Exec Time Memory
0_000.txt AC 1 ms 256 KB
0_001.txt AC 1 ms 256 KB
0_002.txt AC 1 ms 256 KB
1_003.txt AC 1 ms 256 KB
1_004.txt AC 1 ms 256 KB
1_005.txt AC 1 ms 256 KB
1_006.txt AC 1 ms 256 KB
1_007.txt AC 1 ms 256 KB
1_008.txt AC 1 ms 256 KB
1_009.txt AC 1 ms 256 KB
1_010.txt AC 1 ms 256 KB
2_011.txt AC 2 ms 896 KB
2_012.txt AC 2 ms 896 KB
2_013.txt AC 2 ms 1024 KB
2_014.txt AC 2 ms 1024 KB
2_015.txt AC 2 ms 896 KB
2_016.txt AC 2 ms 1024 KB
2_017.txt AC 2 ms 1024 KB
2_018.txt AC 2 ms 1024 KB