Submission #1188553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188553		yoav_s	Coreputer (IOI23_coreputer)	C++20	0 / 100	0 ms	408 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);
}

std::vector<int> malfunctioning_cores(int Nn) {
	srand(time(0));
	realN = Nn;
	ll N = 16;
	v perm(N);
	for (ll i = 0; i < N; i++) perm[i] = i;
	random_shuffle(all(perm));
	v half;
	v secondHalf;
	for (ll j = 0; j < 4; j++)
	{
		v choice, notChosen;
		for (ll i = 0; i < N; i++) if (i & (1 << j)) choice.pb(perm[i]);
		else notChosen.pb(perm[i]);
		if (wrapper(choice) == 0)
		{
			half = choice;
			secondHalf = notChosen;
			break;
		}
	}
	assert(half.size() > 0);
	ll compareTo = half[0];
	v heavier;
	v lighter;
	v equal;
	for (ll x : secondHalf)
	{
		half[0] = x;
		ll res = wrapper(half);
		if (res == -1) lighter.pb(x);
		else if (res == 0) equal.pb(x);
		else heavier.pb(x);
	}
	half[0] = compareTo;
	bool isHeavy = (heavier.size() == 0);
	v fakes;
	for (ll x : heavier) fakes.pb(x);
	for (ll x : equal)
		if (isHeavy)
			fakes.pb(x);
	//assert(fakes.size() > 0);
	ll secondCompareTo = fakes[0];
	ll heavyCount = isHeavy;
	ll secondHeavyCount = fakes.size();
	for (ll i = 2; i < N / 2; i++)
	{
		ll t = half[i];
		half[i] = secondCompareTo;
		ll res = wrapper(half);
		if (res == 0)
		{
			fakes.pb(t);
			heavyCount++;
		}
		half[i] = t;
	}
	if (isHeavy) fakes.pb(half[0]);
	if (heavyCount < secondHeavyCount) fakes.pb(half[1]);
	vector<int> res(realN, 0);
	for (ll x : fakes) res[x] = 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: 0 / 20
• Subtask 2: 0 / 40
• Subtask 3: 0 / 40