oj.uz

Submission #911915

# Submission time Handle Problem Language Result Execution time Memory
911915 2024-01-19T06:14:57 Z dsyz Coreputer (IOI23_coreputer) C++17
20 / 100
 1 ms 592 KB 
#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;
		}
	} //answer is high
	ll checked = -1e18;
	ll parity = 0; //parity of total number of malfunctioning cores
	vector<ll> malfunctioning;
	malfunctioning.push_back(high);
	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;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){
			parity = 0;
			malfunctioning.push_back(i);
		}else if(a == 0){
			parity = 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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct

Subtask #2
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Incorrect 0 ms 344 KB Incorrect
6 Halted 0 ms 0 KB -