Submission #2495166
Source Code Expand
/**************************************
* Au: Hany01
* Email: hany01@foxmail.com
**************************************/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define rep(i, j) for (register int i = 0, i##_end_ = j; i < i##_end_; ++ i)
#define For(i, j ,k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define SZ(a) ((int)(a.size()))
#define ALL(a) a.begin(), a.end()
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define Mod (1000000007)
#define y1 wozenmezhemecaia
#ifdef hany01
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif
template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
inline int read() {
register char c_; register int _, __;
for (_ = 0, __ = 1, c_ = getchar(); !isdigit(c_); c_ = getchar()) if (c_ == '-') __ = -1;
for ( ; isdigit(c_); c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);
return _ * __;
}
const int maxn = 500005;
struct SAM
{
int ch[26], fa, len;
}t[maxn << 1];
int sz[maxn << 1], tot = 1, las = 1, sum[maxn << 1], per[maxn << 1], c[maxn];
int n;
char s[maxn];
inline void extend(int c)
{
register int np = ++ tot, p = las;
las = tot, t[np].len = t[p].len + 1, sz[np] = 1;
while (p && !t[p].ch[c]) t[p].ch[c] = np, p = t[p].fa;
if (!p) t[np].fa = 1;
else {
register int q = t[p].ch[c];
if (t[q].len == t[p].len + 1) t[np].fa = q;
else {
register int nq = ++ tot;
t[nq] = t[q], t[nq].len = t[p].len + 1;
t[np].fa = t[q].fa = nq;
while (p && t[p].ch[c] == q) t[p].ch[c] = nq, p = t[p].fa;
}
}
}
void dfs(int u, int k)
{
if (k <= sz[u]) return ;
k -= sz[u];
rep(i, 26) if (t[u].ch[i])
{
if (sum[t[u].ch[i]] >= k)
{
putchar(i + 97);
dfs(t[u].ch[i], k);
return ;
} else k -= sum[t[u].ch[i]];
}
}
int main()
{
#ifdef hany01
File("c");
#endif
int ty, k;
//Init
scanf("%s", s), n = strlen(s);
ty = 0, k = read();
rep(i, n) extend(s[i] - 97);
//Sort
For(i, 1, tot) ++ c[t[i].len];
For(i, 1, n) c[i] += c[i - 1];
For(i, 1, tot) per[c[t[i].len] --] = i;
//Deal with the requirement
if (ty) {
Fordown(i, tot, 1) sz[t[per[i]].fa] += sz[per[i]];
sz[1] = 0;
} else For(i, 2, tot) sz[i] = 1;
//Get the sum
Fordown(i, tot, 1) {
sum[per[i]] = sz[per[i]];
rep(c, 26) sum[per[i]] += sum[t[per[i]].ch[c]];
}
//Print
if (k > sum[1]) puts("-1");
else dfs(1, k);
return 0;
}
Submission Info
Submission Time
2018-05-12 21:03:56+0900
Task
C - K-th Substring
User
Hany01
Language
C++14 (GCC 5.4.1)
Score
300
Code Size
3161 Byte
Status
AC
Exec Time
3 ms
Memory
10496 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:95:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s), n = strlen(s);
^
Judge Result
Set Name
Sample
Subtask
All
Score / Max Score
0 / 0
200 / 200
100 / 100
Status
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
3 ms
8448 KB
0_001.txt
AC
3 ms
8448 KB
0_002.txt
AC
3 ms
8448 KB
1_003.txt
AC
3 ms
8448 KB
1_004.txt
AC
3 ms
8448 KB
1_005.txt
AC
3 ms
8448 KB
1_006.txt
AC
3 ms
8448 KB
1_007.txt
AC
3 ms
8448 KB
1_008.txt
AC
3 ms
8448 KB
1_009.txt
AC
3 ms
8448 KB
1_010.txt
AC
3 ms
8448 KB
2_011.txt
AC
3 ms
10496 KB
2_012.txt
AC
3 ms
10496 KB
2_013.txt
AC
3 ms
10496 KB
2_014.txt
AC
3 ms
10496 KB
2_015.txt
AC
3 ms
10496 KB
2_016.txt
AC
3 ms
10496 KB
2_017.txt
AC
3 ms
10496 KB
2_018.txt
AC
3 ms
10496 KB