Submission #912096

#	Time	Username	Problem	Language	Result	Execution time	Memory
912096		dsyz	Coreputer (IOI23_coreputer)	C++17	100 / 100	1 ms	428 KiB

coreputer

#include <bits/stdc++.h>
#include "coreputer.h"
using namespace std;
using ll = long long;
#define MAXN (1000005)
 
vector<int> malfunctioning_cores(int N) {
	ll high = N - 1;
	ll low = -1;
	while(high - low > 1){ //binary search for leftmost position such that prefix sum of malfunctioning cores > half of total malfunctioning cores
		ll mid = (high + low) / 2;
		vector<int> T;
		for(ll i = 0;i <= mid;i++){
			T.push_back(i);
		}
		ll a = run_diagnostic(T);
		if(a == 1){
			high = mid;
		}else{
			low = mid;
		}
	}
	ll checked = 1;
	ll parity = 0; //parity of total number of malfunctioning cores
	vector<ll> malfunctioning;
	malfunctioning.push_back(high);
	if(high == N - 1){ //hard code this case (from 0 to N - 2, there are total of 0 or 1 malfunctioning cores)
		vector<int> T;
		T.push_back(high);
		if(run_diagnostic(T) == 0){ //there is 1 malfunctioning core among 0 to N - 2
			ll Lb = 0, Ub = N - 2;
			while(Lb != Ub){
				ll mid = (Lb + Ub) / 2;
				T.clear();
				for(ll i = Lb;i <= mid;i++){
					T.push_back(i);
				}
				if(run_diagnostic(T) == 0){
					Ub = mid;
				}else{
					Lb = mid + 1;
				}
			}
			malfunctioning.push_back(Lb);
		}
	}else{
		for(ll i = 0;i < high;i++){
			if(checked == 15){
				if((ll(malfunctioning.size()) % 2) == parity){
					checked++;
				}else{
					checked++;
					malfunctioning.push_back(i);
				}
				break;
			}
			vector<int> T;
			for(ll j = 0;j <= high;j++){
				if(i == j) continue;
				T.push_back(j);
			}
			ll a = run_diagnostic(T);
			if(a == 0){
				parity = 0;
				malfunctioning.push_back(i);
			}else if(a == -1){
				parity = 1;
				malfunctioning.push_back(i);
			}
			checked++;
		}
		for(ll i = high + 1;i < N && ll(malfunctioning.size()) >= 2;i++){
			if(checked == 15){
				if((ll(malfunctioning.size()) % 2) == parity){
					checked++;
				}else{
					checked++;
					malfunctioning.push_back(i);
				}
				break;
			}
			vector<int> T;
			for(ll j = high;j < N;j++){
				if(i == j) continue;
				T.push_back(j);
			}
			ll a = run_diagnostic(T);
			if(a == -1){
				malfunctioning.push_back(i);
			}
			checked++;
		}
	}
	vector<int> ans;
	for(ll i = 0;i < N;i++){
		ans.push_back(0);
	}
	for(auto u : malfunctioning){
		ans[u] = 1;
	}
	return ans;
}

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