結果
問題 | No.382 シャイな人たち (2) |
ユーザー | 👑 hos.lyric |
提出日時 | 2020-03-28 11:56:10 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 181 ms / 8,000 ms |
コード長 | 5,026 bytes |
コンパイル時間 | 1,400 ms |
コンパイル使用メモリ | 110,000 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-10 17:13:00 |
合計ジャッジ時間 | 4,875 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 175 ms
6,812 KB |
testcase_01 | AC | 148 ms
6,944 KB |
testcase_02 | AC | 137 ms
6,940 KB |
testcase_03 | AC | 118 ms
6,944 KB |
testcase_04 | AC | 138 ms
6,940 KB |
testcase_05 | AC | 125 ms
6,940 KB |
testcase_06 | AC | 181 ms
6,940 KB |
testcase_07 | AC | 120 ms
6,944 KB |
testcase_08 | AC | 120 ms
6,940 KB |
testcase_09 | AC | 169 ms
6,940 KB |
testcase_10 | AC | 124 ms
6,940 KB |
testcase_11 | AC | 103 ms
6,940 KB |
testcase_12 | AC | 137 ms
6,940 KB |
testcase_13 | AC | 111 ms
6,944 KB |
testcase_14 | AC | 137 ms
6,940 KB |
testcase_15 | AC | 109 ms
6,940 KB |
testcase_16 | AC | 133 ms
6,944 KB |
testcase_17 | AC | 81 ms
6,940 KB |
testcase_18 | AC | 101 ms
6,940 KB |
testcase_19 | AC | 104 ms
6,940 KB |
testcase_20 | AC | 2 ms
6,940 KB |
ソースコード
// #pragma GCC optimize ("Ofast") // #pragma GCC optimize ("unroll-loops") // #pragma GCC target ("avx") #include <cassert> #include <cmath> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <functional> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; using Int = long long; template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } int popcnt(__uint128_t x) { return __builtin_popcountll(static_cast<uint64_t>(x)) + __builtin_popcountll(static_cast<uint64_t>(x >> 64)); } Int counter=0; struct IndSet { static constexpr int MAX_N = 128; int n; __uint128_t adj[MAX_N]; int optLen; int opt[MAX_N], us[MAX_N]; int psLens[MAX_N]; int pss[MAX_N + 1][MAX_N]; __uint128_t groups[MAX_N]; IndSet(int n) : n(n), adj(), optLen(0), psLens() { assert(n <= MAX_N); } void addEdge(int u, int v) { // cerr<<u<<" "<<v<<endl; adj[u] |= static_cast<__uint128_t>(1) << v; adj[v] |= static_cast<__uint128_t>(1) << u; } void dfs(int len) { ++counter; // cerr<<"dfs "<<len<<"; us = ";pv(us,us+len); // cerr<<"dfs "<<len<<"; ";for(int i=0;i<psLens[len];++i){cerr<<"("<<(pss[len][i]>>8)<<","<<(pss[len][i]&0xff)<<") ";}cerr<<endl; if (psLens[len] == 0) { if (optLen < len) { optLen = len; std::memcpy(opt, us, sizeof(us[0]) * len); } return; } std::sort(pss[len], pss[len] + psLens[len]); // std::sort(pss[len], pss[len] + psLens[len], [](const int &x, const int &y) { return ((x >> 8) < (y >> 8)); }); // std::sort(pss[len], pss[len] + psLens[len], [](const int &x, const int &y) { return ((x >> 8) > (y >> 8)); }); // cerr<<" ";for(int i=0;i<psLens[len];++i){cerr<<"("<<(pss[len][i]>>8)<<","<<(pss[len][i]&0xff)<<") ";}cerr<<endl; std::memset(groups, 0, sizeof(groups[0]) * psLens[len]); for (int i = psLens[len] - 1; i >= 0; --i) { // for (int i = 0; i < psLens[len]; ++i) { const int u = pss[len][i] & 0xff; for (int color = 0; ; ++color) { if (!(groups[color] & ~adj[u])) { groups[color] |= static_cast<__uint128_t>(1) << u; pss[len][i] |= color << 16; break; } } } std::sort(pss[len], pss[len] + psLens[len]); // std::sort(pss[len], pss[len] + psLens[len], [](const int &x, const int &y) { return ((x >> 16) < (y >> 16)); }); // cerr<<" ";for(int i=0;i<psLens[len];++i){cerr<<"("<<(pss[len][i]>>16)<<","<<((pss[len][i]>>8)&0xff)<<","<<(pss[len][i]&0xff)<<") ";}cerr<<endl; for (int i = psLens[len] - 1; i >= 0; --i) { if (optLen >= len + 1 + (pss[len][i] >> 16)) { break; } const int u = pss[len][i] & 0xff; __uint128_t sub = 0; psLens[len + 1] = 0; for (int j = 0; j < i; ++j) { const int v = pss[len][j] & 0xff; if (!(adj[u] & static_cast<__uint128_t>(1) << v)) { sub |= static_cast<__uint128_t>(1) << v; pss[len + 1][psLens[len + 1]++] = v; } } for (int j = 0; j < psLens[len + 1]; ++j) { const int v = pss[len + 1][j]; pss[len + 1][j] |= (n - popcnt(adj[v] & sub)) << 8; } us[len] = u; dfs(len + 1); } } int run() { std::memset(psLens, 0, sizeof(psLens[0]) * (n + 1)); for (int u = 0; u < n; ++u) { pss[0][psLens[0]++] = (n - popcnt(adj[u])) << 8 | u; } optLen = 0; dfs(0); std::sort(opt, opt + optLen); return optLen; } }; int main() { Int S; for (; ~scanf("%lld", &S); ) { S = (S * 12345) % 1000003; const int N = (S % 120) + 2; S = (S * 12345) % 1000003; const Int P = S; vector<vector<Int>> F(N, vector<Int>(N)); for (int u = 0; u < N; ++u) { for (int v = u + 1; v < N; ++v) { S = (S * 12345) % 1000003; F[u][v] = F[v][u] = S; } } cerr<<"N = "<<N<<", P = "<<P<<endl; // cerr<<"F = "<<endl;for(int u=0;u<N;++u)pv(F[u].begin(),F[u].end()); counter=0; IndSet ind(N); for (int u = 0; u < N; ++u) for (int v = u + 1; v < N; ++v) { if (F[u][v] >= P) { ind.addEdge(u, v); } } const int res = ind.run(); cerr<<"counter = "<<counter<<endl; if (res == N) { puts("-1"); } else { printf("%d\n", res + 1); for (int j = 0; j < res; ++j) { if (j > 0) printf(" "); printf("%d", ind.opt[j] + 1); } puts(""); } } return 0; }