Submission #905426

#	Time	Username	Problem	Language	Result	Execution time	Memory
905426		joonwu04	The Big Prize (IOI17_prize)	C++17	0 / 100	6 ms	2004 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], u=0;
// u = sum of cheapest V's left and right

bool isDiamond(int i);
void makeLR(int i);
int findDiamond(int st, int ed, int maxLR);

int sub2(int n) { // idx: 0 ~ n-1
	for(int i=0; i<n; i++) {
		ls[i] = -1; rs[i] = -1;
	}
	
	// find leftMost candy and rightMost candy
	int st = 0, maxLR=-1, idx=-1;
	while(/*st <= n-1 &&*/ st <= 1000) {
		makeLR(st);
		
		// check if it is dia
		if(isDiamond(st)) return st;
		
		// if no then record maxlr
		if(ls[st] + rs[st] >= maxLR) {
			maxLR = ls[st] + rs[st];
			idx = st;
		}
		st++;
	}
	st = idx;
	
	int ed = n-1;
	while(1) {
		makeLR(ed);
		
		// check if it is dia
		if(isDiamond(ed)) return ed;
		
		// if find rightMost candy
		if(ls[ed] + rs[ed] == maxLR) break;
		ed--;
	}
	printf("OK\n");
	
	return findDiamond(st, ed, maxLR);
}

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];
}

// st, ed are cheapest
int findDiamond(int st, int ed, int maxLR) {
	if(st == ed) {
		if(ls[st] + rs[st] == 0) return st;
		else return -1; 
	}
	
	// if st~ed, no prize
	if(ls[ed] - ls[st] == 0) return -1;
	
	int mid = (st + ed) / 2;
	makeLR(mid);
	if(isDiamond(mid)) return mid;
	
	// make led, rst
	int led = mid;
	while(/*led>=st*/ls[led] + rs[led] < maxLR) {
		led--;
		makeLR(led);
		if(isDiamond(led)) return led;
	}
	
	int rst = mid;
	while(/*rst<=ed*/ls[rst] + rs[rst] < maxLR) {
		rst++;
		makeLR(rst);
		if(isDiamond(rst)) return rst;
	}
	
	int resL = findDiamond(st, led, maxLR);	// check initial condition
	int resR = findDiamond(rst, ed, maxLR);
	
	if(resL != -1) return resL;
	else if(resR != -1) return resR;
	else return -1;
}

int find_best(int n) {
	return sub2(n-1);
}

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