結果
問題 | No.2895 Zero XOR Subset |
ユーザー | kakel-san |
提出日時 | 2024-10-03 23:37:43 |
言語 | C# (.NET 8.0.203) |
結果 |
AC
|
実行時間 | 115 ms / 2,000 ms |
コード長 | 3,666 bytes |
コンパイル時間 | 16,091 ms |
コンパイル使用メモリ | 169,496 KB |
実行使用メモリ | 230,100 KB |
最終ジャッジ日時 | 2024-10-03 23:38:09 |
合計ジャッジ時間 | 20,981 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 48 ms
29,944 KB |
testcase_01 | AC | 47 ms
29,944 KB |
testcase_02 | AC | 111 ms
72,920 KB |
testcase_03 | AC | 49 ms
30,336 KB |
testcase_04 | AC | 49 ms
30,464 KB |
testcase_05 | AC | 50 ms
30,336 KB |
testcase_06 | AC | 113 ms
72,680 KB |
testcase_07 | AC | 50 ms
30,336 KB |
testcase_08 | AC | 109 ms
72,792 KB |
testcase_09 | AC | 53 ms
31,352 KB |
testcase_10 | AC | 58 ms
30,464 KB |
testcase_11 | AC | 49 ms
30,336 KB |
testcase_12 | AC | 111 ms
72,792 KB |
testcase_13 | AC | 56 ms
31,232 KB |
testcase_14 | AC | 58 ms
30,592 KB |
testcase_15 | AC | 115 ms
72,800 KB |
testcase_16 | AC | 54 ms
31,360 KB |
testcase_17 | AC | 49 ms
30,464 KB |
testcase_18 | AC | 110 ms
72,804 KB |
testcase_19 | AC | 54 ms
31,360 KB |
testcase_20 | AC | 50 ms
30,336 KB |
testcase_21 | AC | 50 ms
30,336 KB |
testcase_22 | AC | 54 ms
31,232 KB |
testcase_23 | AC | 58 ms
30,336 KB |
testcase_24 | AC | 49 ms
30,336 KB |
testcase_25 | AC | 54 ms
31,360 KB |
testcase_26 | AC | 115 ms
72,804 KB |
testcase_27 | AC | 53 ms
30,320 KB |
testcase_28 | AC | 56 ms
31,232 KB |
testcase_29 | AC | 115 ms
72,672 KB |
testcase_30 | AC | 54 ms
31,360 KB |
testcase_31 | AC | 54 ms
31,360 KB |
testcase_32 | AC | 110 ms
72,796 KB |
testcase_33 | AC | 53 ms
31,360 KB |
testcase_34 | AC | 111 ms
72,672 KB |
testcase_35 | AC | 58 ms
30,336 KB |
testcase_36 | AC | 112 ms
230,100 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (91 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static int NN => int.Parse(ReadLine()); static long[] NList => ReadLine().Split().Select(long.Parse).ToArray(); public static void Main() { Solve(); } static void Solve() { var n = NN; var a = NList; for (var i = 0; i < n; ++i) if (a[i] == 0) { WriteLine(1); WriteLine(i + 1); return; } var bitmax = 60; if (a.Length > bitmax + 1) { n = bitmax + 1; a = a.Take(n).ToArray(); } var map = new int[bitmax][]; for (var i = 0; i < bitmax; ++i) { map[i] = new int[n + 1]; for (var j = 0; j < n; ++j) map[i][j] = (int)((a[j] >> i) & 1); } GaussJordanEliminationXor(map); var ans = Check(map); if (ans.Length == 0) WriteLine(-1); else { var a2 = new List<int>(); for (var i = 0; i < ans.Length; ++i) if (ans[i] != 0) a2.Add(i + 1); WriteLine(a2.Count); WriteLine(string.Join(" ", a2)); } } // XOR(= mod2の足し算)で掃き出し法を行う static void GaussJordanEliminationXor(int[][] map) { // 標準系にする var px = -1; for (var j = 0; j < map[0].Length - 1; ++j) { var x = px + 1; if (x >= map.Length) break; var sw = -1; for (var i = x; i < map.Length; ++i) if (map[i][j] != 0) { sw = i; break; } if (sw < 0) continue; if (x != sw) (map[x], map[sw]) = (map[sw], map[x]); for (var i = 0; i < map.Length; ++i) if (i != x) { if (map[i][j] != 0) { for (var p = j; p < map[i].Length; ++p) map[i][p] = (map[i][p] + map[x][p]) & 1; } } px = x; } } // 掃き出し法の結果から解を求める static int[] Check(int[][] map) { var n = map[0].Length - 1; var iskey = new bool[n]; var isfree = new bool[n]; for (var i = 0; i < map.Length; ++i) { var flg = true; for (var j = 0; j < n; ++j) if (map[i][j] != 0) { if (flg) { iskey[j] = true; } else { isfree[j] = true; } flg = false; } // 解なしチェック if (flg && map[i][^1] != 0) return new int[0]; } var ans = new int[n]; // (この問題のみ) // freeがない場合解なし // freeのうち最初のみ1に設定し、あとは0に設定 if (isfree.All(f => !f)) return new int[0]; for (var i = 0; i < n; ++i) if (isfree[i]) { ans[i] = 1; break; } for (var i = 0; i < map.Length; ++i) { var pos = -1; for (var j = 0; j < n; ++j) if (map[i][j] != 0) { if (pos < 0) pos = j; else { ans[pos] = (ans[pos] + ans[j]) % 2; } } if (pos >= 0) ans[pos] = (ans[pos] + map[i][^1]) % 2; } return ans; } }