Submission #1147105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147105		maya_s	Coreputer (IOI23_coreputer)	C++20	100 / 100	0 ms	408 KiB

coreputer

#include<bits/stdc++.h>
#include "coreputer.h"
using namespace std;
typedef int ll;

vector<int> malfunctioning_cores(int n) {
	vector<ll> v, ans(n);
	set<ll> s;
	ll lo = 0, hi = n-1;
	while(lo <= hi){
		ll mid = (lo + hi)/2;
		vector<ll> u;
		for(ll i = 0; i <= mid; i++) u.push_back(i);
		ans[mid] = run_diagnostic(u);
		if(ans[mid] == -1) lo = mid+1;
		else hi = mid-1;
	}
	if(lo == 0){
		vector<ll> x(n); x[0] = 1;
		if(ans[lo] == 1) return x;
		lo = 1, hi = n-1;
		while(lo <= hi){
			ll mid = (lo + hi)/2;
			vector<ll> u;
			for(ll i = 0; i <= mid; i++) u.push_back(i);
			ans[mid] = run_diagnostic(u);
			if(ans[mid] <= 0) lo = mid+1;
			else hi = mid-1;
		}
		x[lo] = 1;
		return x;
	}
	if(lo == n-1){
		vector<ll> x(n); x[n-1] = 1;
		return x;
	}
	for(ll i = 0; i < lo; i++) v.push_back(i);
	for(ll i = lo+1; i < n; i++){
		v.push_back(i);
		ans[i] = run_diagnostic(v);
		if(ans[i] == -1) continue;
		v.pop_back();
	}
	v.clear();
	for(ll i = n-1; i > lo; i--) v.push_back(i);
	for(ll i = lo-1; i > 0; i--){
		v.push_back(i);
		ans[i] = run_diagnostic(v);
		if(ans[i] <= (ans[lo] == 0 ? 0 : -1)) {ans[i] = -1; continue;}
		v.pop_back();
	}
	ans[0] = 0;
	ll lo_val = ans[lo];
	for(ll i = 1; i < n; i++){
		if(ans[i] == -1) ans[i] = 0;
		else ans[i] = 1;
	}
	ll cnt_start = 0, cnt_end = 0;
	for(ll i = lo-1; i > 0; i--) if(ans[i] == 1) cnt_start++;
	for(ll i = lo+1; i < n; i++) if(ans[i] == 1) cnt_end++;
	if(lo_val == 0){
		if(cnt_start != cnt_end - 1) ans[0] = 1;
	}
	else{
		if(cnt_start != cnt_end) ans[0] = 1;
	}
	return ans;
}

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