luogu#P12044. [USTCPC 2025] Algorithm Duel

    ID: 36294 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>2025Special Judge线性代数高斯消元线性基构造高校校赛bitset

[USTCPC 2025] Algorithm Duel

题目背景

考虑到评测机性能差异,改为 1s 时限。USTCPC 时限为 3s。

题目描述

Algorithm Duel (在线算法题单挑)是大家非常喜欢的活动之一。而这样的团建活动称为 Algorithm Duel 团建活动(以下简称团建活动)。

社团群内共有 nn 位群友。克露丝卡尔酱从题库中挑选了 m=3n3m=3n-3 道题目,每位群友都有至少其中的一些题没有做过。①

一场标准的团建活动定义如下:对于 mm 道题目中的任意一道题目,有偶数位群友没有做过这道题目,这样他们能两两配对举行 Algorithm Duel。

克露丝卡尔酱很遗憾地发现无论从 nn 位群友挑选任何非空子集,都不能进行一场标准的团建活动。②

但是,她还是非常想举办一场 Algorithm Duel 团建活动,她作为活动负责人只能亲自加入该场活动。为了尽可能保证活动的公正性,她可以任意选择 nmn+1n\sim m-n+1 道题目给一位群友送分(即这些题目可以有奇数位位群友没有做过这道题目)。这样的活动称为非标准的团建活动

好了,现在请帮助她决定应该邀请哪些群友参加这场活动能成为一场非标准的团建活动吧?应该能有解的,不是吗?

输入格式

第一行一个整数 n(2n1000)n(2\le n\le 1000)m=3n3m=3n-3

接下来 nn 行长度为 mm 的 01 串 sssj=1s_j=1 则表示编号为 ii 的群友没有做过题目 jjsj=0s_j=0 则表示编号为 ii 的群友做过题目 jj

保证输入的数据满足题面中①②的条件。

输出格式

输出的第一行一个正整数 k(1kn)k(1\le k\le n),表示邀请的群友的数目。

输出的第二行 kk 个正整数 x1,x2,,xkx_1,x_2,\dots,x_k,表示邀请了编号为 x1,x2,xkx_1,x_2,\dots x_k 的群友参加活动。

要求 1xin1\le x_i\le nxix_i 两两不同。

2
011
110
2
1 2
4
110000000
001100000
000011000
000000111
2
3 4

提示

对于样例 11,邀请所有群友后,有题目 1133 两道题目只有奇数个群友没有做过。n=2n=2 时,非标准的团建活动必须恰好 22 道题目有奇数个群友没有做过,满足条件。