답안 #432211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
432211	2021-06-18T03:12:18 Z	Belgutei	커다란 상품 (IOI17_prize)	C++17	90 / 100	105 ms	1156 KB

prize

#include "prize.h"
#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
 
vector<int> v; 
map<int,pair<int,int> > mp;
bool check[200005];
int ans,mx,N;
 
 
void dfs(int x, int y){
	if(x>y || y>=N) return;
	int a,b,c,d;
	if(check[x]==1){
		a=mp[x].ff;
		b=mp[x].ss;
	}
	else{
		vector<int> v1=ask(x);
		a=v1[0];
		b=v1[1];
		check[x]=1;
		mp[x].ff=a;
		mp[x].ss=b;
	}
	if(x==y){
		if(a+b!=mx) v.pb(x);
		return;
	}
	if(check[y]==1){
		c=mp[y].ff;
		d=mp[y].ss;
	}
	else{
		vector<int> v2=ask(y);
		c=v2[0];
		d=v2[1];
		mp[y].ff=c;
		mp[y].ss=d;
		check[y]=1;
	}
	if(a+b==mx && c+d==mx){
		if(c-a==0 || y-x==1) return;
		int mid=(x+y)/2;
		dfs(x,mid);
		dfs(mid+1,y);
	}
	else{
		if(a+b<mx && c+d<mx){
			v.pb(x);
			v.pb(y);
			if(y-x>=3){
				int mid=(((y-1)+(x+1))/2);
				dfs(x+1,mid);
				dfs(mid+1,y-1);
			}
			if(y-x==2){
				dfs(x+1,x+1);
			}
			return;
		}
		if(a+b<mx){
			v.pb(x);
			if(x+1<y){
				int mid=(x+1+y)/2;
				dfs(x+1,mid);
				dfs(mid+1,y);
			}
			return;
		}
		v.pb(y);
		if(x<y-1){
			int mid=(x-1+y)/2;
			dfs(x,mid);
			dfs(mid+1,y-1);
		}
	}
}
 
int find_best(int n) {
	N=n;
	for(int i=0; i<min(480,n); i++){
		vector<int> vv;
		vv=ask(i);
		check[i]=1;
		mp[i].ff=vv[0];
		mp[i].ss=vv[1];
		mx=max(mx,vv[0]+vv[1]);
	}
	int l=0;
	int r=n-1;
	dfs(l,r);
	for(int i=0; i<v.size(); i++){
		if(check[v[i]]==1){
			if(mp[v[i]].ff+mp[v[i]].ss==0){
				return v[i];
			}
			continue;
		}
	}
	return -1;
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:100:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for(int i=0; i<v.size(); i++){
      |               ~^~~~~~~~~

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	280 KB	Output is correct
2	Correct	10 ms	280 KB	Output is correct
3	Correct	6 ms	308 KB	Output is correct
4	Correct	6 ms	268 KB	Output is correct
5	Correct	3 ms	316 KB	Output is correct
6	Correct	6 ms	288 KB	Output is correct
7	Correct	7 ms	288 KB	Output is correct
8	Correct	6 ms	300 KB	Output is correct
9	Correct	5 ms	296 KB	Output is correct
10	Correct	8 ms	304 KB	Output is correct

Subtask #2

70.0 / 80.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	304 KB	Output is correct
2	Correct	7 ms	320 KB	Output is correct
3	Correct	3 ms	292 KB	Output is correct
4	Correct	7 ms	320 KB	Output is correct
5	Correct	5 ms	328 KB	Output is correct
6	Correct	3 ms	312 KB	Output is correct
7	Correct	7 ms	200 KB	Output is correct
8	Correct	6 ms	200 KB	Output is correct
9	Correct	5 ms	284 KB	Output is correct
10	Correct	8 ms	328 KB	Output is correct
11	Correct	8 ms	504 KB	Output is correct
12	Correct	7 ms	500 KB	Output is correct
13	Correct	14 ms	540 KB	Output is correct
14	Correct	26 ms	448 KB	Output is correct
15	Partially correct	68 ms	884 KB	Partially correct - number of queries: 7832
16	Partially correct	82 ms	924 KB	Partially correct - number of queries: 8270
17	Partially correct	105 ms	884 KB	Partially correct - number of queries: 8271
18	Partially correct	89 ms	896 KB	Partially correct - number of queries: 8320
19	Partially correct	43 ms	952 KB	Partially correct - number of queries: 7868
20	Partially correct	31 ms	820 KB	Partially correct - number of queries: 5498
21	Partially correct	73 ms	920 KB	Partially correct - number of queries: 8249
22	Partially correct	46 ms	868 KB	Partially correct - number of queries: 6513
23	Correct	9 ms	412 KB	Output is correct
24	Correct	9 ms	516 KB	Output is correct
25	Partially correct	78 ms	912 KB	Partially correct - number of queries: 7547
26	Partially correct	68 ms	880 KB	Partially correct - number of queries: 7455
27	Correct	9 ms	408 KB	Output is correct
28	Partially correct	83 ms	916 KB	Partially correct - number of queries: 7497
29	Partially correct	63 ms	800 KB	Partially correct - number of queries: 6391
30	Partially correct	68 ms	1000 KB	Partially correct - number of queries: 8246
31	Partially correct	73 ms	940 KB	Partially correct - number of queries: 8187
32	Correct	17 ms	556 KB	Output is correct
33	Correct	1 ms	200 KB	Output is correct
34	Partially correct	84 ms	1028 KB	Partially correct - number of queries: 8287
35	Correct	9 ms	448 KB	Output is correct
36	Partially correct	87 ms	940 KB	Partially correct - number of queries: 8308
37	Correct	17 ms	412 KB	Output is correct
38	Correct	6 ms	320 KB	Output is correct
39	Partially correct	83 ms	884 KB	Partially correct - number of queries: 8251
40	Partially correct	61 ms	984 KB	Partially correct - number of queries: 7267
41	Partially correct	75 ms	1128 KB	Partially correct - number of queries: 8272
42	Partially correct	97 ms	944 KB	Partially correct - number of queries: 8272
43	Partially correct	86 ms	928 KB	Partially correct - number of queries: 8073
44	Partially correct	89 ms	924 KB	Partially correct - number of queries: 8265
45	Partially correct	70 ms	904 KB	Partially correct - number of queries: 7484
46	Partially correct	65 ms	988 KB	Partially correct - number of queries: 8304
47	Partially correct	43 ms	952 KB	Partially correct - number of queries: 7584
48	Partially correct	89 ms	948 KB	Partially correct - number of queries: 8269
49	Partially correct	78 ms	984 KB	Partially correct - number of queries: 8323
50	Partially correct	82 ms	952 KB	Partially correct - number of queries: 8274
51	Partially correct	80 ms	944 KB	Partially correct - number of queries: 8253
52	Partially correct	76 ms	972 KB	Partially correct - number of queries: 8320
53	Correct	8 ms	408 KB	Output is correct
54	Partially correct	97 ms	976 KB	Partially correct - number of queries: 8250
55	Partially correct	48 ms	1044 KB	Partially correct - number of queries: 8300
56	Partially correct	94 ms	936 KB	Partially correct - number of queries: 8328
57	Partially correct	101 ms	1036 KB	Partially correct - number of queries: 8265
58	Partially correct	63 ms	1156 KB	Partially correct - number of queries: 8257
59	Partially correct	96 ms	924 KB	Partially correct - number of queries: 8302
60	Partially correct	81 ms	904 KB	Partially correct - number of queries: 8251
61	Correct	9 ms	412 KB	Output is correct
62	Correct	10 ms	412 KB	Output is correct
63	Correct	6 ms	344 KB	Output is correct
64	Correct	6 ms	336 KB	Output is correct
65	Correct	8 ms	296 KB	Output is correct
66	Correct	9 ms	292 KB	Output is correct
67	Correct	11 ms	272 KB	Output is correct
68	Correct	6 ms	328 KB	Output is correct
69	Correct	12 ms	272 KB	Output is correct
70	Correct	9 ms	284 KB	Output is correct
71	Partially correct	82 ms	1024 KB	Partially correct - number of queries: 8581
72	Correct	17 ms	448 KB	Output is correct
73	Partially correct	100 ms	956 KB	Partially correct - number of queries: 8476
74	Partially correct	89 ms	1068 KB	Partially correct - number of queries: 8521
75	Correct	7 ms	328 KB	Output is correct
76	Partially correct	81 ms	828 KB	Partially correct - number of queries: 7501
77	Partially correct	57 ms	984 KB	Partially correct - number of queries: 8139
78	Correct	17 ms	440 KB	Output is correct
79	Correct	44 ms	728 KB	Output is correct
80	Partially correct	76 ms	1072 KB	Partially correct - number of queries: 8189
81	Partially correct	73 ms	976 KB	Partially correct - number of queries: 8177
82	Partially correct	46 ms	1076 KB	Partially correct - number of queries: 8131
83	Correct	7 ms	328 KB	Output is correct
84	Partially correct	90 ms	984 KB	Partially correct - number of queries: 6847
85	Partially correct	64 ms	916 KB	Partially correct - number of queries: 8078
86	Correct	7 ms	424 KB	Output is correct
87	Correct	6 ms	320 KB	Output is correct
88	Correct	6 ms	328 KB	Output is correct
89	Correct	6 ms	312 KB	Output is correct
90	Correct	10 ms	312 KB	Output is correct
91	Correct	8 ms	300 KB	Output is correct
92	Correct	6 ms	328 KB	Output is correct
93	Correct	12 ms	484 KB	Output is correct
94	Correct	12 ms	484 KB	Output is correct
95	Correct	15 ms	392 KB	Output is correct
96	Correct	13 ms	440 KB	Output is correct
97	Correct	5 ms	320 KB	Output is correct