Submission #2504539


Source Code Expand

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

char ss[5010];
int k, s[5010], sa[5010], rk[5010], height[5010];

int g(int x, int n0)
{
	return x < n0 ? x * 3 + 1 : (x - n0) * 3 + 2;
}
void radix(int *a, int *b, int *s, int n, int K)
{
	int *hh = new int[K + 1];
	for (int i = 0; i <= K; i++)
		hh[i] = 0;
	for (int i = 0; i < n; i++)
		hh[s[a[i]]]++;
	for (int i = 1; i <= K; i++)
		hh[i] += hh[i - 1];
	for (int i = n - 1; i >= 0; i--)
		b[--hh[s[a[i]]]] = a[i];
}
void dc3(int *s, int *sa, int n, int K)
{
	int n0 = (n + 2) / 3, n1 = (n + 1) / 3, n2 = n / 3, n02 = n0 + n2;
	int *s12 = new int[n02 + 3];
	s12[n02] = s12[n02 + 1] = s12[n02 + 2] = 0;
	int *sa12 = new int[n02 + 3];
	sa12[n02] = sa12[n02 + 1] = sa12[n02 + 2] = 0;
	int *s0 = new int[n0];
	int *sa0 = new int[n0];
	for (int i = 0, hh = 0; i < n; i++)
		if (i % 3)
			s12[hh++] = i;
	if (n % 3 == 1)
		s12[n02 - 1] = n;
	radix(s12, sa12, s + 2, n02, K);
	radix(sa12, s12, s + 1, n02, K);
	radix(s12, sa12, s, n02, K);
	int name = 0, c1 = -1, c2 = -1, c3 = -1;
	for (int i = 0; i < n02; i++)
	{
		if (c1 != s[sa12[i]] || c2 != s[sa12[i] + 1] || c3 != s[sa12[i] + 2])
		{
			c1 = s[sa12[i]];
			c2 = s[sa12[i] + 1];
			c3 = s[sa12[i] + 2];
			name++;
		}
		if (sa12[i] % 3 == 1)
			s12[sa12[i] / 3] = name;
		else
			s12[sa12[i] / 3 + n0] = name;
	}
	if (name < n02)
	{
		// s12[n02] = s12[n02 + 1] = s12[n02 + 2] = 0;
		dc3(s12, sa12, n02, name);
		for (int i = 0; i < n02; i++)
			s12[sa12[i]] = i + 1;
	}
	else
	{
		for (int i = 0; i < n02; i++)
			sa12[s12[i] - 1] = i;
	}
	for (int i = 0, hh = 0; i < n02; i++)
		if (sa12[i] < n0)
			s0[hh++] = sa12[i] * 3;
	radix(s0, sa0, s, n0, K);
	int i = n0 - n1, j = 0, hh = 0;
	while (i < n02 && j < n0)
	{
		if (sa12[i] < n0 && make_pair(s[g(sa12[i], n0)], s12[sa12[i] + n0]) < make_pair(s[sa0[j]], s12[sa0[j] / 3]) ||
			sa12[i] >= n0 && make_tuple(s[g(sa12[i], n0)], s[g(sa12[i], n0) + 1], s12[sa12[i] + 1 - n0]) < make_tuple(s[sa0[j]], s[sa0[j] + 1], s12[sa0[j] / 3 + n0]))
			sa[hh++] = g(sa12[i++], n0);
		else
			sa[hh++] = sa0[j++];
	}
	while (i < n02)
		sa[hh++] = g(sa12[i++], n0);
	while (j < n0)
		sa[hh++] = sa0[j++];
	delete[] s12;
	delete[] sa12;
	delete[] s0;
	delete[] sa0;
}
int main()
{
    scanf("%s%d", ss, &k);
    int n = strlen(ss);
    for (int i = 0; i < n; i++) s[i] = ss[i] - 'a' + 1;
    dc3(s, sa, n, 26);/*
    for (int i = 0; i < n; i++)
    {
        for (int j = sa[i]; j < n; j++) printf("%c", ss[j]);
        puts("");
    }*/
    sa[n] = n;
    for (int i = 0; i < n; i++)
        rk[sa[i]] = i;
    for (int i = 0, k = 0; i < n; i++)
    {
        if (k) k--;
        int j = sa[rk[i] + 1];
        while (s[i + k] == s[j + k])
            k++;
        height[rk[i]] = k;
    }
    for (int i = 0; i < n; i++)
    {
        int hh = i ? height[i - 1] : 0;
        if (k > n - sa[i] - hh) k -= n - sa[i] - hh;
        else
        {
            // printf("%d %d %d\n", i, sa[i], k);
            for (int j = 0; j < k + hh; j++)
                printf("%c", ss[sa[i] + j]);
            break;
        }
    }
    puts("");
}

Submission Info

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

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:91:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s%d", ss, &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 384 KB
2_012.txt AC 2 ms 384 KB
2_013.txt AC 2 ms 384 KB
2_014.txt AC 2 ms 384 KB
2_015.txt AC 1 ms 384 KB
2_016.txt AC 2 ms 384 KB
2_017.txt AC 2 ms 384 KB
2_018.txt AC 2 ms 384 KB