atcoder#ABC280H. [ABC280Ex] Substring Sort
[ABC280Ex] Substring Sort
Score : points
Problem Statement
You are given strings . Let $M = \displaystyle\sum_{i=1}^N \frac{|S_i|(|S_i|+1)}{2}$. For a string and integers and , let us denote by the substring consisting of the -th through -th characters of .
A sequence of triples of integers $((K_1, L_1, R_1), (K_2, L_2, R_2), \ldots, (K_M, L_M, R_M))$ of length satisfies the following conditions:
- The elements are pairwise distinct.
- For all , it holds that and .
- For all , it holds that in the lexicographical order.
You are given integers between and , inclusive. For each , find a possible instance of . We can prove that there always exists a sequence of triples that satisfies the conditions. If multiple triples satisfy the conditions, print any of them. In addition, among different 's, the conforming sequence of triples does not have to be common.
What is the lexicographical order?
Two strings S and T are said to be S \leq T in the lexicographical order if and only if one of the following conditions is satisfied:- |S| \leq |T| and S = T[1, |S|].
- There exists 1\leq k\leq \min(|S|, |T|) such that the i-th characters of S and T are the same for all 1\leq i\leq k-1, and the k-th character of S is alphabetically strictly smaller than that of T.
Constraints
- $\displaystyle\sum_{i=1}^N \lvert S_i\rvert\leq 10^5$
- $1 \leq x_1
- are integers.
- is a string consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
Output
Print lines. The -th line should contain an instance of conforming , separated by spaces. If multiple triples satisfy the conditions, print any of them.
2
abab
cab
2
5 14
1 3 4
2 1 1
We have . One possible sequence of triples that satisfies the conditions is
$((1,1,1), (1,3,3), (2,2,2), (1,1,2), (1,3,4), (2,2,3), (1,1,3), (1,1,4), (1,2,2), (1,4,4), (2,3,3), (1,2,3), (1,2,4), (2,1,1), (2,1,2), (2,1,3))$.
The corresponding sequence of for these in this order is (a
, a
, a
, ab
, ab
, ab
, aba
, abab
, b
, b
, b
, ba
, bab
, c
, ca
, cab
).
Note that the sequence satisfies the conditions even if we swap the -th element with the -th or -th one, so will also be accepted.
3
a
a
ba
2
1 2
1 1 1
1 1 1
We have . The sequence of triples that satisfies the conditions can be or , for example.
Note that, for that you print, the conforming sequence whose -th element is does not have to be common among different ; in other words, there does not necessarily have to exist a sequence whose "-th element is for all ."
10
gxgpuamkx
szhkbpphykin
ezplvfja
mopodotkrj
rimlvumuar
nexcfyce
eurgvjyos
dhvuyfvt
nrdyluacvra
ggwnpnzij
6
74 268 310 380 455 489
3 1 2
4 4 5
4 3 7
9 6 6
6 6 6
2 2 12