Submission #910037

#	Time	Username	Problem	Language	Result	Execution time	Memory
910037		joonwu04	The Big Prize (IOI17_prize)	C++17	100 / 100	32 ms	2136 KiB

prize

#include "prize.h"
#include <iostream>
 
using namespace std;
 
int sub1(int st, int ed) {
	int mid = (st + ed) / 2;
	vector<int> v = ask(mid);
	int l = v[0], r = v[1];
	if(l == 1) return sub1(st, mid-1);
	else if(r == 1) return sub1(mid+1, ed);
	else return mid;
}
 
int ls[200100], rs[200100], maxLR;
// u = sum of cheapest V's left and right
 
bool isDiamond(int i);
void makeLR(int i);
int findDiamond(int st, int ed);
 
int sub2(int n) { // idx: 0 ~ n-1
	for(int i=0; i<n; i++) {
		ls[i] = -1; rs[i] = -1;
	}
	makeLR(0);
	if(isDiamond(0)) return 0;
	makeLR(n-1);
	if(isDiamond(n-1)) return n-1;
	
	return findDiamond(0, n-1);
}
 
bool isDiamond(int i) {
	return ls[i] + rs[i] == 0;
}

void makeLR(int i) {
	if(ls[i] != -1 && rs[i] != -1) return;
	
	vector<int> v = ask(i);
	ls[i] = v[0]; rs[i] = v[1];
}
 
int findDiamond(int st, int ed) {
	if(ed - st <= 1) return -1;
	
	// else
	if(ls[st] + rs[st] == ls[ed] + rs[ed]) {
		// if st~ed, no prize
		if(ls[ed] - ls[st] == 0) return -1;	
		
		// else
		int mid = (st + ed) / 2;
		makeLR(mid);
		if(isDiamond(mid)) return mid;
		
		int resL = findDiamond(st, mid);	// check initial condition
		int resR = findDiamond(mid, ed);
		
		return resL > resR ? resL:resR;
	}
	else if(ls[st] + rs[st] < ls[ed] + rs[ed]) {
		makeLR(st+1);
		if(isDiamond(st+1)) return st+1;
		else return findDiamond(st+1, ed);
	}
	else {
		makeLR(ed-1);
		if(isDiamond(ed-1)) return ed-1;
		else return findDiamond(st, ed-1);
	}	
}
 
int find_best(int n) {
	return sub2(n);
}

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80