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

提出ソース

結果

問題	No.382 シャイな人たち (2)
ユーザー	anta
提出日時	2016-06-23 20:43:25
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	258 ms / 8,000 ms
コード長	6,527 bytes
コンパイル時間	2,276 ms
コンパイル使用メモリ	188,284 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-10-11 18:50:07
合計ジャッジ時間	6,476 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	258 ms 5,248 KB
testcase_01	AC	162 ms 5,248 KB
testcase_02	AC	148 ms 5,248 KB
testcase_03	AC	148 ms 5,248 KB
testcase_04	AC	155 ms 5,248 KB
testcase_05	AC	133 ms 5,248 KB
testcase_06	AC	176 ms 5,248 KB
testcase_07	AC	124 ms 5,248 KB
testcase_08	AC	168 ms 5,248 KB
testcase_09	AC	246 ms 5,248 KB
testcase_10	AC	129 ms 5,248 KB
testcase_11	AC	84 ms 5,248 KB
testcase_12	AC	128 ms 5,248 KB
testcase_13	AC	160 ms 5,248 KB
testcase_14	AC	151 ms 5,248 KB
testcase_15	AC	82 ms 5,248 KB
testcase_16	AC	120 ms 5,248 KB
testcase_17	AC	90 ms 5,248 KB
testcase_18	AC	96 ms 5,248 KB
testcase_19	AC	129 ms 5,248 KB
testcase_20	AC	2 ms 5,248 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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);
		BitSet initSet;
		vector<pair<int, int>> degreeOrder(N);
		for(int i = 0; i < N; ++ i) {
			initSet.set(i);
			degreeOrder[i] = make_pair(-(int)graph[i].count(), i);
		}
		sort(degreeOrder.begin(), degreeOrder.end());
		globalBuffer.resize(N * N + N + N * 2 * N);
		levelVertices.resize(N);
		rep(i, N)
			levelVertices[i].first = globalBuffer.data() + i * N;
		Vertex *initOrder = globalBuffer.data() + N * N,
			*nextBuffer = initOrder + N;
		rep(i, N)
			initOrder[i] = degreeOrder[i].second;

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

		rec(initSet, initOrder, N, nextBuffer);
		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;

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

		Vertex *order = buffer, *levelOffsets = buffer + numVertices,
			*nextBuffer = levelOffsets + numLevels;
		for(int k = 0; k < numLevels; ++ k)
			levelVertices[k].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;
			}
		}
		numVertices = 0;
		for(int k = 0; k < numLevels; ++ k) {
			levelOffsets[k] = numVertices;
			auto p = levelVertices[k];
			for(int i = 0; i < p.second; ++ i)
				order[numVertices ++] = p.first[i];
		}

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

			int u = order[-- numVertices];

			curClique.set(u), ++ curSize;

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

	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;
	vector<pair<Vertex*, int>> levelVertices;
	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);
		//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;
}

yukicoder

結果

テストケース

ソースコード