A10585 | 80-th Level Archeology
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
Archeologists have found a secret pass in the dungeon of one of the pyramids of Cycleland. To enter the treasury they have to open an unusual lock on the door. The lock consists of $n$ words, each consisting of some hieroglyphs. The wall near the lock has a round switch. Each rotation of this switch changes the hieroglyphs according to some rules. The instruction nearby says that the door will open only if words written on the lock would be sorted in lexicographical order (the definition of lexicographical comparison in given in notes section).
The rule that changes hieroglyphs is the following. One clockwise rotation of the round switch replaces each hieroglyph with the next hieroglyph in alphabet, i.e. hieroglyph $x$ ( $1<=x<=c-1$ ) is replaced with hieroglyph $(x+1)$ , and hieroglyph $c$ is replaced with hieroglyph $1$ .
Help archeologist determine, how many clockwise rotations they should perform in order to open the door, or determine that this is impossible, i.e. no cyclic shift of the alphabet will make the sequence of words sorted lexicographically.
The rule that changes hieroglyphs is the following. One clockwise rotation of the round switch replaces each hieroglyph with the next hieroglyph in alphabet, i.e. hieroglyph $x$ ( $1<=x<=c-1$ ) is replaced with hieroglyph $(x+1)$ , and hieroglyph $c$ is replaced with hieroglyph $1$ .
Help archeologist determine, how many clockwise rotations they should perform in order to open the door, or determine that this is impossible, i.e. no cyclic shift of the alphabet will make the sequence of words sorted lexicographically.
输入格式
The first line of the input contains two integers $n$ and $c$ ( $2<=n<=500000$ , $1<=c<=10^{6}$ ) — the number of words, written on the lock, and the number of different hieroglyphs.
Each of the following $n$ lines contains the description of one word. The $i$ -th of these lines starts with integer $l_{i}$ ( $1<=l_{i}<=500000$ ), that denotes the length of the $i$ -th word, followed by $l_{i}$ integers $w_{i,1}$ , $w_{i,2}$ , ..., $w_{i,li}$ ( $1<=w_{i,j}<=c$ ) — the indices of hieroglyphs that make up the $i$ -th word. Hieroglyph with index $1$ is the smallest in the alphabet and with index $c$ — the biggest.
It's guaranteed, that the total length of all words doesn't exceed $10^{6}$ .
Each of the following $n$ lines contains the description of one word. The $i$ -th of these lines starts with integer $l_{i}$ ( $1<=l_{i}<=500000$ ), that denotes the length of the $i$ -th word, followed by $l_{i}$ integers $w_{i,1}$ , $w_{i,2}$ , ..., $w_{i,li}$ ( $1<=w_{i,j}<=c$ ) — the indices of hieroglyphs that make up the $i$ -th word. Hieroglyph with index $1$ is the smallest in the alphabet and with index $c$ — the biggest.
It's guaranteed, that the total length of all words doesn't exceed $10^{6}$ .
输出格式
If it is possible to open the door by rotating the round switch, print integer $x$ ( $0<=x<=c-1$ ) that defines the required number of clockwise rotations. If there are several valid $x$ , print any of them.
If it is impossible to open the door by this method, print $-1$ .
If it is impossible to open the door by this method, print $-1$ .
输入输出样例
输入 #1
4 3 2 3 2 1 1 3 2 3 1 4 2 3 1 2
输出 #1
1
输入 #2
2 5 2 4 2 2 4 2
输出 #2
0
输入 #3
4 4 1 2 1 3 1 4 1 2
输出 #3
-1
Word $a_{1},a_{2},...,a_{m}$ of length $m$ is lexicographically not greater than word $b_{1},b_{2},...,b_{k}$ of length $k$ , if one of two conditions hold:
- at first position $i$ , such that $a_{i}≠b_{i}$ , the character $a_{i}$ goes earlier in the alphabet than character $b_{i}$ , i.e. $a$ has smaller character in the first position where they differ;
- if there is no such position $i$ and $m<=k$ , i.e. the first word is a prefix of the second or two words are equal.
The sequence of words is said to be sorted in lexicographical order if each word (except the last one) is lexicographically not greater than the next word.
In the first sample, after the round switch is rotated $1$ position clockwise the words look as follows:
In the last sample, one can check that no shift of the alphabet will work.
- at first position $i$ , such that $a_{i}≠b_{i}$ , the character $a_{i}$ goes earlier in the alphabet than character $b_{i}$ , i.e. $a$ has smaller character in the first position where they differ;
- if there is no such position $i$ and $m<=k$ , i.e. the first word is a prefix of the second or two words are equal.
The sequence of words is said to be sorted in lexicographical order if each word (except the last one) is lexicographically not greater than the next word.
In the first sample, after the round switch is rotated $1$ position clockwise the words look as follows:
<br></br>1 3<br></br>2<br></br>3 1 2<br></br>3 1 2 3<br></br>In the second sample, words are already sorted in lexicographical order.In the last sample, one can check that no shift of the alphabet will work.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted