A11744 | Hyperspace Jump (hard)
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
It is now 125 years later, but humanity is still on the run from a humanoid-cyborg race determined to destroy it. Or perhaps we are getting some stories mixed up here... In any case, the fleet is now smaller. However, in a recent upgrade, all the navigation systems have been outfitted with higher-dimensional, linear-algebraic jump processors.
Now, in order to make a jump, a ship's captain needs to specify a subspace of the $d$ -dimensional space in which the events are taking place. She does so by providing a generating set of vectors for that subspace.
Princess Heidi has received such a set from the captain of each of $m$ ships. Again, she would like to group up those ships whose hyperspace jump subspaces are equal. To do so, she wants to assign a group number between $1$ and $m$ to each of the ships, so that two ships have the same group number if and only if their corresponding subspaces are equal (even though they might be given using different sets of vectors).
Help Heidi!
Now, in order to make a jump, a ship's captain needs to specify a subspace of the $d$ -dimensional space in which the events are taking place. She does so by providing a generating set of vectors for that subspace.
Princess Heidi has received such a set from the captain of each of $m$ ships. Again, she would like to group up those ships whose hyperspace jump subspaces are equal. To do so, she wants to assign a group number between $1$ and $m$ to each of the ships, so that two ships have the same group number if and only if their corresponding subspaces are equal (even though they might be given using different sets of vectors).
Help Heidi!
输入格式
The first line of the input contains two space-separated integers $m$ and $d$ ( $2<=m<=30000$ , $1<=d<=5$ ) – the number of ships and the dimension of the full underlying vector space, respectively. Next, the $m$ subspaces are described, one after another. The $i$ -th subspace, which corresponds to the $i$ -th ship, is described as follows:
The first line contains one integer $k_{i}$ ( $1<=k_{i}<=d$ ). Then $k_{i}$ lines follow, the $j$ -th of them describing the $j$ -th vector sent by the $i$ -th ship. Each of the $j$ lines consists of $d$ space-separated integers $a_{j}$ , $j=1,...,d$ , that describe the vector ; it holds that $|a_{j}|<=250$ . The $i$ -th subspace is the linear span of these $k_{i}$ vectors.
The first line contains one integer $k_{i}$ ( $1<=k_{i}<=d$ ). Then $k_{i}$ lines follow, the $j$ -th of them describing the $j$ -th vector sent by the $i$ -th ship. Each of the $j$ lines consists of $d$ space-separated integers $a_{j}$ , $j=1,...,d$ , that describe the vector ; it holds that $|a_{j}|<=250$ . The $i$ -th subspace is the linear span of these $k_{i}$ vectors.
输出格式
Output $m$ space-separated integers $g_{1},...,g_{m}$ , where  denotes the group number assigned to the $i$ -th ship. That is, for any $1<=i<j<=m$ , the following should hold: $g_{i}=g_{j}$ if and only if the $i$ -th and the $j$ -th subspaces are equal. In addition, the sequence $(g_{1},g_{2},...,g_{m})$ should be lexicographically minimal among all sequences with that property.
输入输出样例
输入 #1
8 2 1 5 0 1 0 1 1 0 1 2 0 6 0 1 2 0 1 1 0 2 -5 -5 4 3 2 1 1 0 1 2 1 0 1 0
输出 #1
1 2 2 2 3 3 3 1
In the sample testcase, the first and the last subspace are equal, subspaces 2 to 4 are equal, and subspaces 5 to 7 are equal.
Recall that two subspaces, one given as the span of vectors  and another given as the span of vectors , are equal if each vector $v_{i}$ can be written as a linear combination of vectors $w_{1},...,w_{k}$ (that is, there exist coefficients  such that $v_{i}=α_{1}w_{1}+...+α_{k}w_{k}$ ) and, similarly, each vector $w_{i}$ can be written as a linear combination of vectors $v_{1},...,v_{n}$ .
Recall that a sequence $(g_{1},g_{2},...,g_{m})$ is lexicographically smaller than a sequence $(h_{1},h_{2},...,h_{m})$ if there exists an index $i$ , $1<=i<=m$ , such that $g_{i}<h_{i}$ and $g_{j}=h_{j}$ for all $j<i$ .
Recall that two subspaces, one given as the span of vectors  and another given as the span of vectors , are equal if each vector $v_{i}$ can be written as a linear combination of vectors $w_{1},...,w_{k}$ (that is, there exist coefficients  such that $v_{i}=α_{1}w_{1}+...+α_{k}w_{k}$ ) and, similarly, each vector $w_{i}$ can be written as a linear combination of vectors $v_{1},...,v_{n}$ .
Recall that a sequence $(g_{1},g_{2},...,g_{m})$ is lexicographically smaller than a sequence $(h_{1},h_{2},...,h_{m})$ if there exists an index $i$ , $1<=i<=m$ , such that $g_{i}<h_{i}$ and $g_{j}=h_{j}$ for all $j<i$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted