#99657 (C++14) No.382 シャイな人たち (2)

• 問題: No.382 シャイな人たち (2)
• ユーザー: anta
• 提出日時: 2016-06-23 23:05:31
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 185 ms / 8,000 ms
• コード長: 7,124 bytes
• コンパイル時間: 2,101 ms
• コンパイル使用メモリ: 182,528 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-10-11 19:02:43
• 合計ジャッジ時間: 5,485 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	185 ms; 5,248 KB
testcase_01	AC	117 ms; 5,248 KB
testcase_02	AC	115 ms; 5,248 KB
testcase_03	AC	135 ms; 5,248 KB
testcase_04	AC	144 ms; 5,248 KB
testcase_05	AC	161 ms; 5,248 KB
testcase_06	AC	181 ms; 5,248 KB
testcase_07	AC	101 ms; 5,248 KB
testcase_08	AC	113 ms; 5,248 KB
testcase_09	AC	140 ms; 5,248 KB
testcase_10	AC	135 ms; 5,248 KB
testcase_11	AC	99 ms; 5,248 KB
testcase_12	AC	90 ms; 5,248 KB
testcase_13	AC	97 ms; 5,248 KB
testcase_14	AC	125 ms; 5,248 KB
testcase_15	AC	90 ms; 5,248 KB
testcase_16	AC	152 ms; 5,248 KB
testcase_17	AC	90 ms; 5,248 KB
testcase_18	AC	123 ms; 5,248 KB
testcase_19	AC	59 ms; 5,248 KB
testcase_20	AC	2 ms; 5,248 KB

ソースコード

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

struct BitSet {
	enum { K = 2, W = 64 };
	uint64_t data[K];

	BitSet() : data{ 0 } {}

	explicit operator bool() const {
		uint64_t r = 0;
		rep(i, K)
			r |= data[i];
		return r != 0;
	}

	bool get(unsigned pos) const {
		return data[pos / W] >> (pos % W) & 1;
	}

	void set(unsigned pos) {
		data[pos / W] |= uint64_t(1) << (pos % W);
	}

	void unset(unsigned pos) {
		data[pos / W] &= ~(uint64_t(1) << (pos % W));
	}

	int count() const {
		int res = 0;
		rep(i, K) res += popcount(data[i]);
		return res;
	}

	BitSet operator&(BitSet that) const {
		BitSet res;
		rep(i, K)
			res.data[i] = data[i] & that.data[i];
		return res;
	}

	bool isIntersectTo(const BitSet &that) const {
		return bool(*this & that);
	}

	int getSingleton() const {
		rep(i, K) if(data[i]) {
			if((data[i] & (data[i] - 1)) != 0)
				return -1;
			for(int j = i + 1; j < K; ++ j)
				if(data[j])
					return -1;
			return i * W + bsf(data[i]);
		}
		return -1;
	}

	static int bsf(uint64_t x) {
#if defined(__GNUC__)
		return __builtin_ctzll(x);
#else
		unsigned long res;
		_BitScanForward64(&res, x);
		return res;
#endif
	}

	static int popcount(uint64_t x) {
#if defined(__GNUC__)
		return __builtin_popcountll(x);
#else
		return (int)__popcnt64(x);
#endif
	}

	std::string toBitString() const {
		std::string res(128, '0');
		for(int i = 0; i < 128; ++ i)
			res[i] = '0' + get(i);
		return res;
	}
};

class MaximumCliqueBranchAndBound {
public:
	typedef uint8_t Vertex;

	BitSet maximumClique(const vector<BitSet> &originalGraph) {
		graph = originalGraph;
		int N = (int)graph.size();
		levels.assign(N, BitSet());
		vertexLevel.assign(N, -1);
		vertexDegree.assign(N, -1);
		BitSet initSet;
		for(int i = 0; i < N; ++ i)
			initSet.set(i);
		globalBuffer.resize(N * N * 2 + N + N * 3 * N);
		levelVertices.resize(N);
		rep(i, N)
			levelVertices[i].first = globalBuffer.data() + i * N;
		degreeVertices.resize(N);
		rep(i, N)
			degreeVertices[i].first = globalBuffer.data() + (N + i) * N;
		Vertex *initOrder = globalBuffer.data() + N * N * 2,
			*nextBuffer = initOrder + N;
		rep(i, N)
			initOrder[i] = i;

		curClique = maxClique = BitSet();
		curSize = maxSize = 0;
		numRecs = 0;

		rec(initSet, initOrder, N, nextBuffer);

		//cerr << "numRecs = " << numRecs << endl;
		return maxClique;
	}

private:

	void rec(BitSet remSet, const Vertex *originalOrder, int originalOrderSize, Vertex *buffer) {
		++ numRecs;

		int numLevels = 0, numVertices = 0;
		for(int ix = 0; ix < originalOrderSize; ++ ix) {
			int p = originalOrder[ix];
			if(!remSet.get(p)) continue;
			++ numVertices;
			int k = 0;
			while(k < numLevels && levels[k].isIntersectTo(graph[p]))
				++ k;
			if(k == numLevels) {
				levels[k] = BitSet();
				++ numLevels;
			}
			levels[k].set(p);
			vertexLevel[p] = k;
			vertexDegree[p] = (remSet & graph[p]).count();

			int threshold = maxSize - curSize;
			if(k > threshold && k == numLevels - 1) {
				reNumber(p, k, threshold);
				if(!levels[k])
					-- numLevels;
			}
		}

		Vertex *levelOrder = buffer,
			*levelOffsets = levelOrder + numVertices,
			*degreeOrder = levelOffsets + numLevels,
			*nextBuffer = degreeOrder + numVertices;
		for(int k = 0; k < numLevels; ++ k)
			levelVertices[k].second = 0;
		for(int d = 0; d < numVertices; ++ d)
			degreeVertices[d].second = 0;

		for(int ix = 0; ix < originalOrderSize; ++ ix) {
			int v = originalOrder[ix];
			if(remSet.get(v)) {
				{
					auto &p = levelVertices[vertexLevel[v]];
					p.first[p.second ++] = v;
				}
				{
					auto &p = degreeVertices[vertexDegree[v]];
					p.first[p.second ++] = v;
				}
			}
		}
		for(int k = 0, num = 0; k < numLevels; ++ k) {
			levelOffsets[k] = num;
			auto p = levelVertices[k];
			for(int i = 0; i < p.second; ++ i)
				levelOrder[num ++] = p.first[i];
		}
		for(int d = numVertices - 1, num = 0; d >= 0; -- d) {
			auto p = degreeVertices[d];
			for(int i = 0; i < p.second; ++ i)
				degreeOrder[num ++] = p.first[i];
		}

		for(int i = numVertices; ; -- i) {
			int threshold = max(maxSize - curSize, 0);
			if(threshold >= numLevels || i <= levelOffsets[threshold])
				break;

			int u = levelOrder[i - 1];

			curClique.set(u), ++ curSize;

			BitSet newSet = remSet & graph[u];
			if(newSet) {
				rec(newSet, degreeOrder, numVertices, nextBuffer);
			} else if(curSize > maxSize) {
				maxClique = curClique, maxSize = curSize;
			}
			curClique.unset(u), -- curSize;
			remSet.unset(u);
		}
	}

	void reNumber(int p, int k, int threshold) {
		for(int i = 0; i < threshold; ++ i) {
			BitSet S = graph[p] & levels[i];
			int q = S.getSingleton();
			if(q == -1) continue;
			for(int j = i + 1; j <= threshold; ++ j) {
				if(graph[q] & levels[j]) continue;
				levels[k].unset(p);
				levels[i].unset(q);
				levels[i].set(p);
				levels[j].set(q);
				vertexLevel[p] = i;
				vertexLevel[q] = j;
				return;
			}
		}
	}

	vector<BitSet> graph;
	BitSet curClique, maxClique;
	int curSize, maxSize;

	vector<BitSet> levels;
	vector<int> vertexLevel, vertexDegree;
	vector<pair<Vertex*, int>> levelVertices;
	vector<pair<Vertex*, int>> degreeVertices;
	vector<Vertex> globalBuffer;
	long long numRecs;
};

//#include "C:\Dropbox\backup\implements\Util\CPUTime.hpp"

int main() {
	int initS;
	while(~scanf("%d", &initS)) {
	//vector<pair<double, int>> list;
	//int initS; for(initS = 1; initS < 1000003; ++initS) {
	//if(initS % 100 == 0)cerr << initS << "..." << endl;
	//for(int initS : vector<int>{ 115398, 267904, 52859, 518145, 66814, 519427, 882073, 670079, 758187, 65005, 31884, 519427 , 552242 , 394304 , 371116 , 626395, 60145, 649 }) CPUTIMEIT("test") {
		int N, P;
		vector<BitSet> g;
		{
			int S = initS;
			S = ((ll)S * 12345) % 1000003;
			N = (S % 120) + 2;
			g.assign(N, BitSet());
			S = ((ll)S * 12345) % 1000003;
			P = S;
			rep(i, N) reu(j, i + 1, N) {
				S = ((ll)S * 12345) % 1000003;
				if(S < P) {
					g[i].set(j);
					g[j].set(i);
				}
			}
		}
		//cerr << initS << " (" << N << ", " << P << ")" << ": ";
		MaximumCliqueBranchAndBound mc;
		//double start = getCPUTime();
		BitSet ans = mc.maximumClique(g);
		//cerr << "time = " << getCPUTime() - start << endl;
		//list.emplace_back(getCPUTime() - start, initS);

		if(ans.count() == N) {
			puts("-1");
		} else {
			printf("%d\n", (int)ans.count() + 1);
			vector<int> v;
			rep(i, N) if(ans.get(i))
				v.push_back(i);
			for(int i : v) for(int j : v) if(i != j)
				assert(g[i].get(j));
			for(int i = 0; i < (int)v.size(); ++ i) {
				if(i != 0) putchar(' ');
				printf("%d", v[i] + 1);
			}
			puts("");
		}
	}
	return 0;
}