QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#558623#7281. How to Avoid Disqualification in 75 Easy Stepsuser10086Compile Error//C++171.9kb2024-09-11 17:12:022024-09-11 17:12:08

Judging History

你现在查看的是最新测评结果

  • [2024-09-11 17:12:08]
  • 评测
  • [2024-09-11 17:12:02]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 1000, MAX = 26;

#define int unsigned

int R[N];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

bool check()
{
	unordered_set<int> all;
	for (int i = 0; i < N; i++)
		for (int j = i; j < N; j++)
		{
			if (!R[i] || !R[j]) continue;
			int val = R[i] | R[j];
			if (all.find(val) != all.end()) return false;
			all.insert(val);
		}
	return true;
}

int rnd()
{
	return rng() % 1000 < 292;
}

int rndi()
{
	int v = 0;
	while (__builtin_popcount(v) < 8) v |= (1 << (rng() % MAX));
	return v;
}

double rand01()
{
	return (double) rng() / rng.max();
}

signed main()
{
	int rd = 0;
	const int B = 1000;
	unordered_set<int> all;
	
	const int SAMP = 1e5;
	
	while (1)
	{
		all.clear(); rd = 0;
	vector<int> pre;
	for (int i = 0; i < (1 << MAX); i++)
		if (__builtin_popcount(i) == 8) pre.push_back(i);
	reverse(pre.begin(), pre.end());
	
	const int SWP = 10;
	for (int i = 0; i < SWP; i++) swap(pre[rng()%pre.size()], pre[rng()%pre.size()]);

	for (int i = 0; i < B; i++)
	{
		int rdd = 0;
		while (!pre.empty())
		{
			rdd++, rd++;
			R[i] = pre.back(); pre.pop_back();
			unordered_set<int> tmp;
			bool flag = true;
			double p = 1;
			for (int j = 0; j <= i; j++)
				if ((tmp.find(R[i] | R[j]) != tmp.end()) || (all.find(R[i] | R[j]) != all.end())) 
				{
					flag = false;
					break;
				}
				else 
				{
					tmp.insert(R[i] | R[j]);
					if (i != j && __builtin_popcount(R[i] & R[j]) >= 6) p *= 0 * exp(1 - (signed)__builtin_popcount(R[i] & R[j]));
				}
			if (flag && rand01() < p)
			{
				for (int j = 0; j <= i; j++)
					all.insert(R[i] | R[j]);
				break;
			}
			else R[i] = 0;
		}
		cerr << i << ' ' << R[i] << endl;
	}
	int i = 0;
	while (R[i]) i++;
	if (i >= 998) break;
	}
	assert(check());
	for (int i = 0; i < N; i++) cout << R[i] << ',';
	cout << endl << rd << ' ' << clock();
}

Details

/usr/bin/ld: /tmp/ccIaQphl.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/cc4eNSwk.o:implementer.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc4eNSwk.o: in function `main':
implementer.cpp:(.text.startup+0x1b): undefined reference to `scout(int, int)'
collect2: error: ld returned 1 exit status