結果
| 問題 | No.382 シャイな人たち (2) |
| ユーザー |
 eitaho
|
| 提出日時 | 2016-08-22 01:16:40 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,472 bytes |
| コンパイル時間 | 1,167 ms |
| コンパイル使用メモリ | 102,320 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-11-07 22:30:27 |
| 合計ジャッジ時間 | 5,218 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 1 WA * 20 |
ソースコード
#include <iostream>#include <sstream>#include <string>#include <vector>#include <stack>#include <queue>#include <set>#include <map>#include <algorithm>#include <cstdio>#include <cstdlib>#include <cstring>#include <cctype>#include <cmath>#include <cassert>#include <climits>#include <numeric>#include <functional>#include <time.h>#include <bitset>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<int, int> Pii;#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define FOR(i, a, b) for (int i = (int)a; i < (int)b; i++)template<class T> void checkmin(T &a, T b) { if (b < a) a = b; }template<class T> void checkmax(T &a, T b) { if (b > a) a = b; }int bitcount64(ll x) {#ifdef _MSC_VERreturn (int)__popcnt64(x);#elsereturn __builtin_popcountll(x);#endif}int rightmost64(ll x) {#ifdef _MSC_VERunsigned long res;_BitScanForward64(&res, x);return res;#elsereturn __builtin_ctzll(x);#endif}struct BitSet {ll M1, M2;BitSet() { M1 = M2 = 0; }BitSet(ll m1, ll m2) { M1 = m1; M2 = m2; }void Set(int i) {if (i < 64) M1 |= 1LL << i;else M2 |= 1LL << i;}void Reset(int i) {if (i < 64) M1 &= ~(1LL << i);else M2 &= ~(1LL << i);}bool Get(int i) {if (i < 64) return (M1 >> i & 1) == 1;else return (M2 >> i & 1) == 1;}int Rightmost() {if (M1 != 0) return rightmost64(M1);else return 64 + rightmost64(M2);}int Single() {if (M2 == 0) {if (M1 != 0 && (M1 & M1 - 1) == 0)return bitcount64((M1 & -M1) - 1);} else if (M1 == 0 && (M2 & M2 - 1) == 0)return 64 + bitcount64((M2 & -M2) - 1);return -1;}BitSet And(BitSet B) { return BitSet(M1 & B.M1, M2 & B.M2); }void Clear() { M1 = M2 = 0; }bool Any() { return (M1 | M2) != 0; }bool Intersect(BitSet B) { return (M1 & B.M1 | M2 & B.M2) != 0; }int Count() { return bitcount64(M1) + bitcount64(M2); }};class MaxCliqueSearcher {public:static const int MaxN = 128;int N;int RecCount;MaxCliqueSearcher(int n) {N = n;}void AddEdge(int a, int b) {E[a].Set(b);E[b].Set(a);}BitSet Search() {AnsCount = RecCount = 0;BitSet rem;for (int i = 0; i < N; i++) rem.Set(i);Rec(Vs, 0, BitSet(), rem);return Ans;}private:BitSet E[MaxN], ColorSet[MaxN];pair<int, int> P[MaxN];BitSet Ans;int AnsCount;int Vs[MaxN * (MaxN + 1)];void Rec(int* buff, int currCount, BitSet selected, BitSet rem) {RecCount++;if (currCount > AnsCount) {AnsCount = currCount;Ans = selected;}if (currCount + rem.Count() <= AnsCount) return;int num;int* cand = SortCand(buff, num, AnsCount - currCount + 1, rem);for (int i = 0; i < num; i++) {int a = cand[i];selected.Set(a);rem.Reset(a);Rec(cand + num, currCount + 1, selected, rem.And(E[a]));selected.Reset(a);}}int* SortCand(int* buff, int& num, int atleast, BitSet rem) {int count = rem.Count(), a = 0; num = 0;SortByDegDescending(buff, rem, count);int numColor = Coloring(atleast, count, buff);if (numColor < atleast) return 0;int ni = 0, startCol = atleast - 1;for (int col = startCol; col < numColor; col++)num += ColorSet[col].Count();for (int col = startCol; col < numColor; col++)for (BitSet set = ColorSet[col]; set.Any(); set.Reset(a)) {a = set.Rightmost();P[ni++] = pair<int, int>(E[a].And(rem).Count(), a);}sort(P, P + num);int* cand = buff + count;for (int i = 0; i < num; i++) cand[i] = P[i].second;return cand;}void SortByDegDescending(int* cand, BitSet rem, int count) {int ni = 0, a = 0;for (BitSet set = rem; set.Any(); set.Reset(a)) {a = set.Rightmost();P[ni++] = pair<int, int>(-E[a].And(rem).Count(), a);}sort(P, P + count);for (int i = 0; i < count; i++) cand[i] = P[i].second;}int Coloring(int atleast, int count, int* vs) {int numColor = 0, a = 0, c;for (int i = 0; i < count; i++) {if (numColor + count - i < atleast) return 0;a = vs[i];c = 0;for (BitSet e = E[a]; c < numColor && e.Intersect(ColorSet[c]); ) c++;if (c == numColor) { ColorSet[c].Clear(); numColor++; }ColorSet[c].Set(a);if (c == numColor - 1 && c == atleast && FixColor(a, c, atleast) && !ColorSet[c].Any())numColor--;}if (numColor == atleast && ColorSet[numColor - 1].Count() <= 3) {for (BitSet set = ColorSet[numColor - 1]; set.Any(); set.Reset(a))if (!FixColor(a = set.Rightmost(), numColor - 1, atleast)) return numColor;numColor--;}return numColor;}bool FixColor(int a, int col, int ub) {BitSet e = E[a];for (int col1 = 0; col1 < ub - 1; col1++) {int b = e.And(ColorSet[col1]).Single();if (b == -1) continue;for (int col2 = col1 + 1; col2 < ub; col2++)if (!E[b].Intersect(ColorSet[col2])) {ColorSet[col].Reset(a);ColorSet[col1].Set(a);ColorSet[col1].Reset(b);ColorSet[col2].Set(b);return true;}}return false;}};int next(int &x) {return x = (int)(x * 12345LL % 1000003);}int solve(int seed) {int N = 2 + next(seed) % 120;MaxCliqueSearcher searcher(N);int P = next(seed);rep(a, N) FOR(b, a + 1, N) if (next(seed) < P) searcher.AddEdge(a, b);BitSet ans = searcher.Search();if (ans.Count() == N) cout << -1 << endl;else {cout << (ans.Count() + 1) << endl;vector<int> vs;rep(i, N) if (ans.Get(i)) vs.push_back(i + 1);rep(i, vs.size()) cout << (i > 0 ? " " : "") << vs[i];cout << endl;}return ans.Count();}int main() {int S;cin >> S;solve(S);return 0;}