제출 #428886

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
428886		vanic	커다란 상품 (IOI17_prize)	C++14	20 / 100	2 ms	396 KiB

prize

#include "prize.h"
#include <iostream>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <unistd.h>
#include <cassert>

using namespace std;

const int maxn=2e5+5;

int sum;
bool asked[maxn];

int nadji(int L, int D, int vall, int vald){
	assert(L!=D);
//	cout << L << ' ' << D << endl;
	int br=0;
	int pos;
	vector < int > v={-1, -1};
	do{
		int br1=0;
		do{
			pos=rand()%(D-L)+L;
			br1++;
		}while(asked[pos] && br1<100);
		if(!asked[pos]){
			v=ask(pos);
			asked[pos]=1;
			if(!v[0] && !v[1]){
				return pos;
			}
		}
		br++;
	}while(br<100 && v[0]+v[1]!=sum);
	if(v[0]+v[1]!=sum){
//		assert(D-L<1000);
		br=0;
		for(int i=L; i<D; i++){
			if(!asked[i]){
				asked[i]=1;
				v=ask(i);
				if(!v[0] && !v[1]){
					return i;
				}
				if(v[0]+v[1]==sum){
					br++;
				}
			}
		}
		assert(br<(D-L)/2);
		return -1;
	}
	br=-1;
	if(v[0]-vall){
		br=nadji(L, pos, vall, v[1]);
		if(br!=-1){
			return br;
		}
	}
	if(v[1]-vald){
		br=nadji(pos+1, D, v[0], vald);
	}
	return br;
}

int find_best(int n){
	srand(time(NULL)*getpid());
	vector < int > v;
	int pos;
	do{
		pos=rand()%n;
		v=ask(pos);
		if(!v[0] && !v[1]){
			return pos;
		}
	}while(v[0]+v[1]>n/2);
	sum=v[0]+v[1];
	int a=nadji(0, n, 0, 0);
	assert(a!=-1);
	return a;
}

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