結果
問題 | No.382 シャイな人たち (2) |
ユーザー |
|
提出日時 | 2020-04-26 10:14:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,436 ms / 8,000 ms |
コード長 | 1,427 bytes |
コンパイル時間 | 543 ms |
コンパイル使用メモリ | 30,464 KB |
最終ジャッジ日時 | 2025-01-10 01:53:50 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:51:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 51 | scanf("%d", &s); | ~~~~~^~~~~~~~~~
ソースコード
#include <cstdio> using u32 = unsigned; using u64 = unsigned long long; using u128 = __uint128_t; u32 step(u32 s){ return (u64) s * 12345 % 1000003; } u128 edges[121]; int ctz(const u128 &n){ if((u64) n){ return __builtin_ctzll((u64) n); } return 64 + __builtin_ctzll((u64) (n >> 64)); } int popc(const u128 &n){ return __builtin_popcountll((u64) n) + __builtin_popcountll((u64) (n >> 64)); } u128 mis(const u128 &g){ if(g == 0) return 0; int y = 127; int d = 0; for(u128 h = g; h; h &= h - 1){ int z = ctz(h); int k = popc(g & edges[z]); if(k <= 2) return mis(g & ~edges[z]) | ((u128) 1 << z); if(k > d){ y = z; d = k; } } u128 g0 = mis(g & ~edges[y]) | ((u128) 1 << y); if(d == 3) return g0; u128 g1 = mis(g & ~((u128) 1 << y)); return popc(g0) > popc(g1) ? g0 : g1; } int main(){ int s; scanf("%d", &s); s = step(s); int n = (s % 120) + 2; s = step(s); int p = s; for(int i = 0; i < n; i++){ edges[i] |= ((u128) 1 << i); for(int j = i+1; j < n; j++){ s = step(s); edges[i] |= ((u128) (s >= p) << j); edges[j] |= ((u128) (s >= p) << i); } } u128 g = mis(((u128) 1 << n) - 1); int smis = popc(g); if(smis == n){ puts("-1"); return 0; } printf("%d\n", popc(g)+1); for(u128 h = g; h; ){ printf("%d", ctz(h) + 1); h &= h - 1; printf("%c", h ? ' ' : '\n'); } return 0; }