結果
| 問題 |
No.382 シャイな人たち (2)
|
| コンテスト | |
| ユーザー |
 eitaho
|
| 提出日時 | 2016-08-21 10:12:50 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,648 bytes |
| コンパイル時間 | 1,554 ms |
| コンパイル使用メモリ | 106,396 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-11-07 22:22:46 |
| 合計ジャッジ時間 | 5,290 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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_VER
return (int)__popcnt64(x);
#else
return __builtin_popcountll(x);
#endif
}
int rightmost64(ll x) {
#ifdef _MSC_VER
unsigned long res;
_BitScanForward64(&res, x);
return res;
#else
return __builtin_ctzll(x);
#endif
}
struct BitSet {
public:
ll M1, M2;
BitSet() { M1 = 0; 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;
}
void Clear() { M1 = M2 = 0; }
bool Intersect(BitSet B) { return (M1 & B.M1 | M2 & B.M2) != 0; }
BitSet And(BitSet B) { return BitSet(M1 & B.M1, M2 & B.M2); }
bool Any() { return (M1 | 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(0, BitSet(), rem);
return Ans;
}
private:
BitSet E[MaxN], ColorSet[MaxN];
BitSet Ans;
int AnsCount;
void Rec(int currCount, BitSet selected, BitSet rem) {
RecCount++;
if (currCount > AnsCount) {
AnsCount = currCount;
Ans = selected;
}
if (currCount + rem.Count() <= AnsCount) return;
vector<int> cand = SortCand(AnsCount - currCount + 1, rem);
for (int a : cand) {
selected.Set(a);
rem.Reset(a);
Rec(currCount + 1, selected, rem.And(E[a]));
selected.Reset(a);
}
}
vector<int> SortCand(int atleast, BitSet rem) {
int count = rem.Count(), a = 0;
vector<int> vs = SortByDegDescending(rem, count);
int numColor = Coloring(atleast, count, vs);
if (numColor < atleast) return vector<int>();
int num = 0, ni = 0, startCol = atleast - 1;
for (int col = startCol; col < numColor; col++)
num += ColorSet[col].Count();
vector<pair<int, int> > cand;
cand.resize(num);
for (int col = startCol; col < numColor; col++)
for (BitSet set = ColorSet[col]; set.Any(); set.Reset(a)) {
a = set.Rightmost();
cand[ni++] = pair<int, int>(E[a].And(rem).Count(), a);
}
sort(cand.begin(), cand.end());
vector<int> res;
res.resize(num);
for (int i = 0; i < num; i++) res[i] = cand[i].second;
return res;
}
vector<int> SortByDegDescending(BitSet rem, int count) {
int ni = 0, a = 0;
vector<pair<int, int> > v;
v.resize(count);
for (BitSet set = rem; set.Any(); set.Reset(a)) {
a = set.Rightmost();
v[ni++] = pair<int, int>(-E[a].And(rem).Count(), a);
}
sort(v.begin(), v.end());
vector<int> res;
res.resize(count);
for (int i = 0; i < count; i++) res[i] = v[i].second;
return res;
}
int Coloring(int atleast, int count, vector<int> &vs) {
int numColor = 0, a = 0, c;
for (int i = 0; i < vs.size(); i++) {
if (numColor + vs.size() - 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);
for (int a = 0; a < N; a++)
for (int b = a + 1; b < N; b++)
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() + 1;
}
int main() {
int S;
cin >> S;
solve(S);
return 0;
}