제출 #559740

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
559740		jamezzz	커다란 상품 (IOI17_prize)	C++17	100 / 100	91 ms	16344 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

int ans,worst;
mt19937 rng(4);

vector<vector<int>> memo;
vector<int> myask(int i){
	if(memo[i][0]!=-1)return memo[i];
	return memo[i]=ask(i);
}

void dnc(vector<int> v,int good,int lgood,int rgood){
	if(good==0)return;
	if(v.size()==0)return;
	
	//printf("dnc: {");
	//for(int i:v)printf("%d ",i);
	//printf("} %d %d %d\n",good,lgood,rgood);
	
	int m=v.size()/2;
	
	vector<int> idk;
	for(int i=0;i<v.size();++i){
		if(memo[v[i]][0]!=-1&&memo[v[i]][0]+memo[v[i]][1]==worst)idk.push_back(i);
	}
	//for(int i:idk)printf("%d ",i);printf("\n");
	if(idk.size()!=0)m=idk[idk.size()/2];
	
	int s=m;
	while(m<v.size()){
		vector<int> res=myask(v[m]);
		if(res[0]+res[1]==0){
			ans=v[m];return;
		}
		if(res[0]+res[1]==worst){
			int mid=m-s;
			vector<int> l,r;
			for(int i=0;i<s;++i)l.push_back(v[i]);
			for(int i=m+1;i<v.size();++i)r.push_back(v[i]);
			dnc(l,res[0]-mid-lgood,lgood,res[1]+mid);
			dnc(r,res[1]-mid-rgood,res[0]+mid,rgood);
			return;
		}
		else ++m;
	}
	
	vector<int> l;
	int mid=m-s;
	for(int i=0;i<s;++i)l.push_back(v[i]);
	dnc(l,good-mid,lgood,rgood+mid);
}

int find_best(int n){
	memo.resize(n);
	for(int i=0;i<n;++i)memo[i].resize(2,-1);
	
	for(int i=0;i<min(n,500);++i){
		int x=rng()%n;
		vector<int> res=myask(x);
		worst=max(worst,res[0]+res[1]);
		if(res[0]+res[1]==0)return x;
	}
	
	vector<int> v;
	for(int i=0;i<n;++i)v.push_back(i);
	
	dnc(v,worst,0,0);
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

prize.cpp: In function 'void dnc(std::vector<int>, int, int, int)':
prize.cpp:25:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i=0;i<v.size();++i){
      |              ~^~~~~~~~~
prize.cpp:32:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  while(m<v.size()){
      |        ~^~~~~~~~~
prize.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |    for(int i=m+1;i<v.size();++i)r.push_back(v[i]);
      |                  ~^~~~~~~~~

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