結果

問題 No.382 シャイな人たち (2)
ユーザー eitahoeitaho
提出日時 2016-08-22 01:16:40
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 147 ms / 8,000 ms
コード長 6,472 bytes
コンパイル時間 1,119 ms
コンパイル使用メモリ 100,820 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-07 17:35:50
合計ジャッジ時間 4,641 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 144 ms
4,376 KB
testcase_01 AC 120 ms
4,376 KB
testcase_02 AC 114 ms
4,376 KB
testcase_03 AC 116 ms
4,376 KB
testcase_04 AC 123 ms
4,376 KB
testcase_05 AC 135 ms
4,376 KB
testcase_06 AC 147 ms
4,380 KB
testcase_07 AC 94 ms
4,380 KB
testcase_08 AC 122 ms
4,376 KB
testcase_09 AC 144 ms
4,376 KB
testcase_10 AC 101 ms
4,380 KB
testcase_11 AC 104 ms
4,376 KB
testcase_12 AC 132 ms
4,376 KB
testcase_13 AC 117 ms
4,376 KB
testcase_14 AC 106 ms
4,380 KB
testcase_15 AC 100 ms
4,376 KB
testcase_16 AC 115 ms
4,376 KB
testcase_17 AC 67 ms
4,376 KB
testcase_18 AC 90 ms
4,376 KB
testcase_19 AC 96 ms
4,376 KB
testcase_20 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 {
    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;
}
0