結果

問題 No.382 シャイな人たち (2)
ユーザー eitahoeitaho
提出日時 2016-08-21 10:12:50
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 6,648 bytes
コンパイル時間 1,536 ms
コンパイル使用メモリ 106,844 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-25 11:06:51
合計ジャッジ時間 4,619 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 2 ms
5,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 {
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;
}
0