Submission #1188600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188600		yoav_s	Coreputer (IOI23_coreputer)	C++20	100 / 100	153 ms	932 KiB

coreputer

#include <bits/stdc++.h>

using namespace std;

typedef int ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef pair<ll, ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()

const ll INF = 1e18;
const ll mod = 1e9 + 7;

int run_diagnostic(std::vector<int> T);

ll realN;

ll wrapper(v T)
{
	vector<int> q;
	for (ll x : T)
	{
		if (x < realN) q.pb(x);
	}
	return run_diagnostic(q);
}
ll evaluate(ll question, v possibleSubsets)
{
    ll smaller = 0, equal = 0, larger = 0;
    for (ll subset : possibleSubsets)
    {
        ll right = question & subset;
        ll wrong = (~question) & subset;
        if (__builtin_popcount(right) > __builtin_popcount(wrong)) larger++;
        else if (__builtin_popcount(right) == __builtin_popcount(wrong)) equal++;
        else smaller++;
    }
    return max<ll>({smaller, equal, larger});
}

std::vector<int> malfunctioning_cores(int Nn) {
	srand(time(0));
	realN = Nn;
	ll n = 16;
    v possibleSubsets(1 << n);
    for (ll i = 0; i < possibleSubsets.size(); i++) possibleSubsets[i] = i;
	while (possibleSubsets.size() > 1)
	{
		ll question = 0;
		for (ll i = 0; i < n; i++) if (rand() % 2) question ^= (1 << i);
		ll ev = evaluate(question, possibleSubsets);
		ll threshold = (possibleSubsets.size() + 1) / 2;
		double T = 1;
		const double mul = 0.9999;
		ll bestQ = question, bestEv = ev;
		ll iterations = 10000;
		while (ev >= threshold && (iterations--))
		{
			v changes; changes.pb(rand() % n);
			if (rand() % 2) changes.pb(rand() % n);
			for (ll x : changes) question ^= (1 << x);
			ll newEv = evaluate(question, possibleSubsets);
			ll threshold = exp((newEv - ev) / T);
			if (threshold == 0) threshold = INF;
			if (newEv < ev || rand() % threshold == 0)
			{
				ev = newEv;
				if (ev < bestEv)
				{
					bestQ = question;
					bestEv = ev;
				}
			}
			else
			{
				for (ll x : changes) question ^= (1 << x);
			}
			T *= mul;
		}
		question = bestQ;
		v query;
		for (ll i = 0; i < n; i++) if (question & (1 << i)) query.pb(i);
		ll resp = wrapper(query);
		v newPoss;
		for (ll subset : possibleSubsets)
		{
			ll right = question & subset;
			ll wrong = (~question) & subset;
			ll ev;
			if (__builtin_popcount(right) > __builtin_popcount(wrong)) ev = 1;
			else if (__builtin_popcount(right) == __builtin_popcount(wrong)) ev = 0;
			else ev = -1;
			if (ev == resp) newPoss.pb(subset);
		}
		possibleSubsets = newPoss;
	}
	v res(realN);
	for (ll j = 0; j < realN; j++) if (possibleSubsets[0] & (1 << j)) res[j] = 1;
	return res;
}
/*

static inline constexpr int maxDiagnostics = 32;
static int diagnostic_counter = 0;
static int malfunctioningCores = 0;

static int N;
static std::vector<int> M;

static inline void protocol_violation(std::string message) {
	printf("Protocol Violation: %s\n", message.c_str());
	exit(0);
}

int run_diagnostic(std::vector<int> T) {
	++diagnostic_counter;
	if (diagnostic_counter > maxDiagnostics) {
		protocol_violation("too many calls");
	}

	int l = T.size();
	if (l > N) {
		protocol_violation("invalid array");
	}

	for (int i = 0; i < l; ++i) {
		if (T[i] < 0 || T[i] >= N) {
			protocol_violation("invalid array");
		}
		for (int j = 0; j < i; ++j) {
			if (T[i] == T[j]) {
				protocol_violation("invalid array");
			}
		}
	}

	int malfunctioningTaggedCores = 0;
    for (int i : T) {
        if (M[i] == 1) malfunctioningTaggedCores++;
    }

    int malfunctioningUntaggedCores = malfunctioningCores - malfunctioningTaggedCores;
    if (malfunctioningTaggedCores > malfunctioningUntaggedCores) {
        return 1;
    }
    if (malfunctioningTaggedCores == malfunctioningUntaggedCores) {
        return 0;
    }
    return -1;
}

int main() {
	assert(1 == scanf("%d", &N));
	M.resize(N);
	for (int i = 0; i < N; ++i) {
		assert(1 == scanf("%d", &M[i]));
		malfunctioningCores += M[i];
	}

	if (malfunctioningCores == 0) {
		printf("No Malfunctioning Core\n");
        exit(0);
	}

	std::vector<int> c = malfunctioning_cores(N);
	int n = c.size();
	for (int i = 0; i < n; ++i) {
		printf(i == 0 ? "%d" : " %d", c[i]);
	}
	printf("\n");
	printf("%d\n", diagnostic_counter);

	return 0;
}
/**/

Compilation message (stderr)

coreputer.cpp:27:16: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   27 | const ll INF = 1e18;
      |                ^~~~

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40