結果

問題 No.382 シャイな人たち (2)
ユーザー 東前頭十一枚目東前頭十一枚目
提出日時 2019-07-12 00:48:41
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,134 bytes
コンパイル時間 1,723 ms
コンパイル使用メモリ 170,236 KB
実行使用メモリ 10,272 KB
最終ジャッジ日時 2024-04-26 15:41:32
合計ジャッジ時間 20,449 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template<int bit>
struct MaximumClique {
	const int V;
	int E = 0;
	bitset<bit> ans;
	vector<bitset<bit>> G;
	MaximumClique(const int V) :
		V(V),
		G(vector<bitset<bit>>(V))
		{}
	bool addEdge(const int from, const int to) {
		if(G[from][to]) return false;
		G[from][to] = G[to][from] = true;
		++E;
		return true;
	}
	void increment(bitset<bit> &mask) {
		for(int i = 0; i < bit; ++i) {
			if(not mask[i]) {
				mask[i] = true;
				return;
			}
			mask[i] = false;
		}
	}
	void reverse() {
		bitset<bit> mask((1ll << V) - 1);
		mask.flip();
		for(int i = 0; i < V; ++i) {
			G[i].flip();
			G[i] ^= mask;
		}
	}
	bitset<bit> build() {
		bitset<bit> mask((1ll << V) - 1);
		return build(mask, E);
	}
	bitset<bit> build(bitset<bit> mask, int E) {
		if(mask.count() < ans.count()) return ans;
		bitset<bit> ret = clique(mask);
		for(int i = 0; i < V; ++i) {
			if(mask[i]) {
				int deg = G[i].count();
				if(deg * deg < 2 * E) {
					bitset<bit> ex;
					for(int j = 0; j < V; ++j) {
						if(G[i][j]) {
							G[i].flip(j);
							G[j].flip(i);
							ex[j] = true;
							--E;
						}
					}
					ret = build(mask.flip(i), E);
					for(int j = 0; j < V; ++j) {
						if(ex[j]) {
							G[i].flip(j);
							G[j].flip(i);
						}
					}
				}
			}
		}
		return (ans = ret);
	}
	bitset<bit> clique(bitset<bit> mask) {
		// cerr << "clique : " << bitset<5>(mask) << endl;
		// for(int i = 0; i < V; ++i) {
		// 	cerr << i << " : " << bitset<5>(G[i]) << endl;
		// }
		const int V = mask.count();
		int node[V];
		for(int i = 0, cnt = 0; i < V; ++i, ++cnt) {
			while(not mask[cnt]) ++cnt;
			node[i] = cnt;
		}
		bitset<bit> ret = ans;
		for(bitset<bit> mask; not mask[V]; increment(mask)) {
			// cerr << "group : " << bitset<5>(mask) << endl;
			if(mask.count() < ret.count()) continue;
			try {
				for(int i = 0; i < V; ++i) {
					if(mask[i]) {
						for(int j = 0; j < V; ++j) {
							if(i == j) continue;
							if(not mask[j]) continue;
							// if(not (((G[node[i]] >> j) & 1) & ((mask >> j) & 1))) {
							if(not G[node[i]][j]) {
								// cerr << i << " diff : " << bitset<5>(G[node[i]]) << endl;
								// cerr << j << " diff : " << bitset<5>(mask) << endl;
								throw "INVALID";
							}
						}
					}
				}
			}
			catch(...) {
				continue;
			}
			ret = mask;
			// cerr << bitset<5>(ret) << endl;
			// ret = (__builtin_popcountll(ret) > __builtin_popcountll(mask) ? ret : mask);
		}
		// cerr << "result : " << bitset<5>(ret) << endl;
		return (ans = ret);
	}
};

int main() {
	const int MOD = 1e6 + 3;
	int64_t s; cin >> s;
	s = s * 12345 % MOD;
	int n = s % 120 + 2;
	MaximumClique<128> mc(n);
	s = s * 12345 % MOD;
	int64_t p = s;
	for(int i = 0; i < n; ++i) {
		for(int j = i + 1; j < n; ++j) {
			s = s * 12345 % MOD;
			if(s >= p) {
				mc.addEdge(i, j);
			}
		}
	}
	mc.reverse();
	mc.build();
	int ans = mc.ans.count() - 1;
	if(ans == n - 1) {
		cout << -1 << '\n';
		return 0;
	}
	cout << ans << '\n';
	for(int i = 1, cnt = 0; i <= n or cnt < ans; ++i) {
		if(mc.ans[i - 1]) {
			cout << i << (cnt == n - 1 ? '\n' : ' ');
			++cnt;
		}
	}
	return 0;
}
0