답안 #339655

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
339655	2020-12-25T19:18:40 Z	ogibogi2004	커다란 상품 (IOI17_prize)	C++14	90 / 100	93 ms	2284 KB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
pair<int,int> answer[MAXN];
vector<int>valuable;
int maxs=0;
pair<int,int>q;
vector<int>lollipops;
char lorv[MAXN];
pair<int,int> get_answer(int i)
{
	//cout<<i<<endl;
	if(answer[i].first!=-1)return answer[i];
	vector<int>q=ask(i);
	answer[i].first=q[0];
	answer[i].second=q[1];
	return answer[i];
}
void bs(int l,int r)
{
	if(l>r)return;
	pair<int,int> ivan=get_answer(l);
	if(l==r)
	{
		if(ivan.first+ivan.second!=maxs)
		{
			valuable.push_back(l);
		}
		return;
	}
	if(ivan.first+ivan.second!=maxs)
	{
		valuable.push_back(l);
		bs(l+1,r);
		return;
	}
	ivan=get_answer(r);
	if(ivan.first+ivan.second!=maxs)
	{
		valuable.push_back(r);
		bs(l,r-1);
		return;
	}
	if(get_answer(r).first==get_answer(l).first)return;
	int mid,low=l,high=r,ans=-1;
	while(low<=high)
	{
		mid=(low+high)/2;
		ivan=get_answer(mid);
		if(ivan.first+ivan.second!=maxs)
		{
			ans=mid;
			break;
		}
		if(ivan.first>get_answer(l).first)
		{
			high=mid-1;
		}
		else low=mid+1;
	}
	if(ans==-1)return;
	valuable.push_back(ans);
	bs(l+1,ans-1);
	bs(ans+1,r);
}
int find_best(int n) {
	if(n<=5000)
	{
		for(int i=0;i<n;i++)
		{
			vector<int>t=ask(i);
			if(t[0]+t[1]==0)
			{
				return i;
			}
		}
	}
	//cout<<"*\n";
	for(int i=0;i<n;i++)answer[i]={-1,-1};
	
	for(int i=0;i<500;i++)
	{
		q=get_answer(i);
		if(q.first+q.second==0)
		{
			/*for(int j=0;j<=200000000;j++)
			{
				j=4*j-3*j;
				answer[j%500]=answer[j%500];
				lorv[j%500]='Z';
			}*/
			return i;
		}
		answer[i]=q;
		maxs=max(maxs,q.first+q.second);
	}
	
	bs(0,n-1);
	
	
	/*for(int i=0;i<n;i++)lorv[i]='?';
	for(int i=0;i<500;i++)
	{
		if(answer[i].first+answer[i].second==maxs)
		{
			lorv[i]='L';
			lollipops.push_back(i);
		}
		else
		{
			lorv[i]='V';
			valuable.push_back(i);
		}
	}
	bs(500,n-1);*/
	//assert(false);
	for(auto j:valuable)
	{
		if(get_answer(j).first+get_answer(j).second==0)
		{
			return j;
		}
	}
	//assert(false);
	return 0;
}

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	1900 KB	Output is correct
2	Correct	6 ms	1900 KB	Output is correct
3	Correct	6 ms	1900 KB	Output is correct
4	Correct	6 ms	1900 KB	Output is correct
5	Correct	8 ms	1900 KB	Output is correct
6	Correct	2 ms	1900 KB	Output is correct
7	Correct	5 ms	1900 KB	Output is correct
8	Correct	6 ms	1900 KB	Output is correct
9	Correct	6 ms	1900 KB	Output is correct
10	Correct	8 ms	1900 KB	Output is correct

Subtask #2

70.0 / 80.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	1900 KB	Output is correct
2	Correct	4 ms	2028 KB	Output is correct
3	Correct	6 ms	1900 KB	Output is correct
4	Correct	6 ms	1900 KB	Output is correct
5	Correct	4 ms	2028 KB	Output is correct
6	Correct	2 ms	1900 KB	Output is correct
7	Correct	4 ms	2028 KB	Output is correct
8	Correct	8 ms	1900 KB	Output is correct
9	Correct	6 ms	1900 KB	Output is correct
10	Correct	6 ms	1900 KB	Output is correct
11	Correct	13 ms	2028 KB	Output is correct
12	Correct	12 ms	2028 KB	Output is correct
13	Correct	12 ms	1900 KB	Output is correct
14	Correct	17 ms	492 KB	Output is correct
15	Partially correct	71 ms	2028 KB	Partially correct - number of queries: 7970
16	Partially correct	87 ms	2028 KB	Partially correct - number of queries: 8429
17	Correct	5 ms	1900 KB	Output is correct
18	Partially correct	85 ms	1900 KB	Partially correct - number of queries: 8460
19	Correct	6 ms	1900 KB	Output is correct
20	Partially correct	53 ms	1188 KB	Partially correct - number of queries: 5613
21	Partially correct	61 ms	1900 KB	Partially correct - number of queries: 7020
22	Partially correct	56 ms	2284 KB	Partially correct - number of queries: 5991
23	Correct	6 ms	1900 KB	Output is correct
24	Correct	7 ms	2028 KB	Output is correct
25	Partially correct	62 ms	1900 KB	Partially correct - number of queries: 7793
26	Partially correct	64 ms	2172 KB	Partially correct - number of queries: 8026
27	Correct	8 ms	1900 KB	Output is correct
28	Partially correct	70 ms	1900 KB	Partially correct - number of queries: 7351
29	Partially correct	49 ms	2028 KB	Partially correct - number of queries: 6153
30	Partially correct	88 ms	1900 KB	Partially correct - number of queries: 8354
31	Correct	7 ms	1900 KB	Output is correct
32	Correct	7 ms	1900 KB	Output is correct
33	Correct	0 ms	364 KB	Output is correct
34	Partially correct	52 ms	1972 KB	Partially correct - number of queries: 7781
35	Correct	9 ms	1900 KB	Output is correct
36	Partially correct	74 ms	1900 KB	Partially correct - number of queries: 7599
37	Correct	11 ms	2028 KB	Output is correct
38	Correct	7 ms	1900 KB	Output is correct
39	Partially correct	75 ms	1900 KB	Partially correct - number of queries: 8362
40	Partially correct	68 ms	1900 KB	Partially correct - number of queries: 7278
41	Partially correct	70 ms	2028 KB	Partially correct - number of queries: 7860
42	Partially correct	72 ms	2028 KB	Partially correct - number of queries: 7860
43	Partially correct	65 ms	2028 KB	Partially correct - number of queries: 6844
44	Partially correct	43 ms	1968 KB	Partially correct - number of queries: 7737
45	Partially correct	70 ms	1900 KB	Partially correct - number of queries: 7992
46	Correct	6 ms	1900 KB	Output is correct
47	Partially correct	65 ms	2160 KB	Partially correct - number of queries: 7833
48	Partially correct	47 ms	2096 KB	Partially correct - number of queries: 8471
49	Partially correct	77 ms	1900 KB	Partially correct - number of queries: 8000
50	Partially correct	85 ms	2156 KB	Partially correct - number of queries: 8461
51	Partially correct	66 ms	1900 KB	Partially correct - number of queries: 7595
52	Partially correct	82 ms	1900 KB	Partially correct - number of queries: 8443
53	Correct	8 ms	1900 KB	Output is correct
54	Partially correct	79 ms	2088 KB	Partially correct - number of queries: 8231
55	Correct	6 ms	1900 KB	Output is correct
56	Partially correct	90 ms	1900 KB	Partially correct - number of queries: 8446
57	Partially correct	65 ms	1900 KB	Partially correct - number of queries: 8105
58	Partially correct	68 ms	1900 KB	Partially correct - number of queries: 7149
59	Partially correct	51 ms	2056 KB	Partially correct - number of queries: 7847
60	Partially correct	56 ms	1900 KB	Partially correct - number of queries: 5899
61	Correct	9 ms	1932 KB	Output is correct
62	Correct	9 ms	1900 KB	Output is correct
63	Correct	8 ms	1900 KB	Output is correct
64	Correct	6 ms	1900 KB	Output is correct
65	Correct	6 ms	1900 KB	Output is correct
66	Correct	11 ms	1900 KB	Output is correct
67	Correct	7 ms	1948 KB	Output is correct
68	Correct	6 ms	1900 KB	Output is correct
69	Correct	7 ms	1948 KB	Output is correct
70	Correct	9 ms	1900 KB	Output is correct
71	Partially correct	74 ms	2028 KB	Partially correct - number of queries: 8739
72	Correct	9 ms	1900 KB	Output is correct
73	Partially correct	72 ms	1900 KB	Partially correct - number of queries: 8616
74	Partially correct	85 ms	2076 KB	Partially correct - number of queries: 8686
75	Correct	7 ms	1900 KB	Output is correct
76	Partially correct	73 ms	1900 KB	Partially correct - number of queries: 7510
77	Partially correct	58 ms	2028 KB	Partially correct - number of queries: 7839
78	Correct	11 ms	1900 KB	Output is correct
79	Correct	31 ms	2028 KB	Output is correct
80	Partially correct	43 ms	1948 KB	Partially correct - number of queries: 8123
81	Partially correct	64 ms	1900 KB	Partially correct - number of queries: 7885
82	Partially correct	68 ms	2028 KB	Partially correct - number of queries: 8169
83	Correct	6 ms	1900 KB	Output is correct
84	Partially correct	84 ms	1900 KB	Partially correct - number of queries: 6917
85	Partially correct	93 ms	1900 KB	Partially correct - number of queries: 8075
86	Correct	8 ms	1900 KB	Output is correct
87	Correct	8 ms	1900 KB	Output is correct
88	Correct	8 ms	1900 KB	Output is correct
89	Correct	7 ms	1900 KB	Output is correct
90	Correct	7 ms	1900 KB	Output is correct
91	Correct	6 ms	1900 KB	Output is correct
92	Correct	7 ms	1900 KB	Output is correct
93	Correct	13 ms	1900 KB	Output is correct
94	Correct	13 ms	1900 KB	Output is correct
95	Correct	7 ms	1948 KB	Output is correct
96	Correct	11 ms	1900 KB	Output is correct
97	Correct	6 ms	1900 KB	Output is correct