답안 #33296 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
33296	2017-10-23T09:19:30 Z	model_code	커다란 상품 (IOI17_prize)	C++11	90 / 100	89 ms	4020 KB

prize

#include<bits/stdc++.h>
#include "prize.h"
#define X first
#define Y second
using namespace std;

typedef pair<int,int> pii;

int numb, q_count = 10000;
pii P[210000];
bool mark[210000];
vector<int>vtmp;

pii query(int x)
{
  if(mark[x]) return P[x];
  mark[x]=true;
  q_count --;
  vtmp=ask(x);
  pii tmp=pii(vtmp[0],vtmp[1]);
  if(tmp.X+tmp.Y==0) throw x;
  return P[x]=tmp;
}

void bs(int l,int r,int nl,int nr)
{
  if(l>r) return;
  for(int i=0;i<=r-l;i++)
    {
      int mid,midl=(l+r)/2-i/2,midr=(l+r)/2+(i+1)/2;
      if(i%2==0) mid=midl;
      else mid=midr;
      pii tmp=query(mid);
      if(tmp.X+tmp.Y==numb)
	{
	  int tmpl=(i%2==0?0:midr-midl);
	  int tmpr=(i%2==1?0:midr-midl);
	  if(tmp.X-tmpl>nl) bs(l,midl-1,nl,tmp.Y+tmpl);
	  if(tmp.Y-tmpr>nr) bs(midr+1,r,tmp.X+tmpr,nr);
	  break;
	}
    }
}

int find_best(int n)
{
  if(n==1) return 0;
  try{
    numb=0;
    memset(mark,false,sizeof mark);
    int p=0;
    for(int i=0;i<sqrt(n)+30 && i<n && numb<27;i++)
      {
	pii tmp=query(i);
	if(tmp.X+tmp.Y>numb) p=i;
	numb=max(numb,tmp.X+tmp.Y);
      }
    bs(p,n-1,p,0);
  }
  catch(int ans){
    for(int i=0;i<q_count;i++)
      ask(0);
    return ans;
  }
  return -1;
}

Subtask #1
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	4020 KB	Output is correct
2	Correct	19 ms	4020 KB	Output is correct
3	Correct	39 ms	4020 KB	Output is correct
4	Correct	39 ms	4020 KB	Output is correct
5	Correct	39 ms	4020 KB	Output is correct
6	Correct	26 ms	4020 KB	Output is correct
7	Correct	23 ms	4020 KB	Output is correct
8	Correct	63 ms	4020 KB	Output is correct
9	Correct	53 ms	4020 KB	Output is correct
10	Correct	26 ms	4020 KB	Output is correct

Subtask #2
70.0 / 80.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	33 ms	4020 KB	number of queries: 10000
2	Incorrect	59 ms	4020 KB	number of queries: 10000
3	Incorrect	73 ms	4020 KB	number of queries: 10000
4	Incorrect	29 ms	4020 KB	number of queries: 10000
5	Incorrect	66 ms	4020 KB	number of queries: 10000
6	Incorrect	66 ms	4020 KB	number of queries: 10000
7	Incorrect	49 ms	4020 KB	number of queries: 10000
8	Incorrect	89 ms	4020 KB	number of queries: 10000
9	Incorrect	33 ms	4020 KB	number of queries: 10000
10	Incorrect	16 ms	4020 KB	number of queries: 10000
11	Incorrect	33 ms	4020 KB	number of queries: 10000
12	Incorrect	46 ms	4020 KB	number of queries: 10000
13	Incorrect	43 ms	4020 KB	number of queries: 10000
14	Incorrect	19 ms	4020 KB	number of queries: 10000
15	Incorrect	33 ms	4020 KB	number of queries: 10000
16	Incorrect	46 ms	4020 KB	number of queries: 10000
17	Incorrect	23 ms	4020 KB	number of queries: 10000
18	Incorrect	53 ms	4020 KB	number of queries: 10000
19	Incorrect	66 ms	4020 KB	number of queries: 10000
20	Incorrect	46 ms	4020 KB	number of queries: 10000
21	Incorrect	19 ms	4020 KB	number of queries: 10000
22	Incorrect	33 ms	4020 KB	number of queries: 10000
23	Incorrect	33 ms	4020 KB	number of queries: 10000
24	Incorrect	49 ms	4020 KB	number of queries: 10000
25	Incorrect	46 ms	4020 KB	number of queries: 10000
26	Incorrect	23 ms	4020 KB	number of queries: 10000
27	Incorrect	36 ms	4020 KB	number of queries: 10000
28	Incorrect	26 ms	4020 KB	number of queries: 10000
29	Incorrect	19 ms	4020 KB	number of queries: 10000
30	Incorrect	39 ms	4020 KB	number of queries: 10000
31	Incorrect	26 ms	4020 KB	number of queries: 10000
32	Incorrect	33 ms	4020 KB	number of queries: 10000
33	Incorrect	33 ms	4020 KB	number of queries: 10000
34	Incorrect	29 ms	4020 KB	number of queries: 10000
35	Incorrect	19 ms	4020 KB	number of queries: 10000
36	Incorrect	46 ms	4020 KB	number of queries: 10000
37	Incorrect	23 ms	4020 KB	number of queries: 10000
38	Incorrect	66 ms	4020 KB	number of queries: 10000
39	Incorrect	23 ms	4020 KB	number of queries: 10000
40	Incorrect	16 ms	4020 KB	number of queries: 10000
41	Incorrect	56 ms	4020 KB	number of queries: 10000
42	Incorrect	46 ms	4020 KB	number of queries: 10000
43	Incorrect	33 ms	4020 KB	number of queries: 10000
44	Incorrect	53 ms	4020 KB	number of queries: 10000
45	Incorrect	43 ms	4020 KB	number of queries: 10000
46	Incorrect	39 ms	4020 KB	number of queries: 10000
47	Incorrect	6 ms	4020 KB	number of queries: 10000
48	Incorrect	26 ms	4020 KB	number of queries: 10000
49	Incorrect	53 ms	4020 KB	number of queries: 10000
50	Incorrect	26 ms	4020 KB	number of queries: 10000
51	Incorrect	49 ms	4020 KB	number of queries: 10000
52	Incorrect	49 ms	4020 KB	number of queries: 10000
53	Incorrect	26 ms	4020 KB	number of queries: 10000
54	Incorrect	43 ms	4020 KB	number of queries: 10000
55	Incorrect	39 ms	4020 KB	number of queries: 10000
56	Incorrect	39 ms	4020 KB	number of queries: 10000
57	Incorrect	49 ms	4020 KB	number of queries: 10000
58	Incorrect	29 ms	4020 KB	number of queries: 10000
59	Incorrect	33 ms	4020 KB	number of queries: 10000
60	Incorrect	23 ms	4020 KB	number of queries: 10000
61	Incorrect	29 ms	4020 KB	number of queries: 10000
62	Incorrect	43 ms	4020 KB	number of queries: 10000
63	Incorrect	23 ms	4020 KB	number of queries: 10000
64	Incorrect	43 ms	4020 KB	number of queries: 10000
65	Incorrect	46 ms	4020 KB	number of queries: 10000
66	Incorrect	53 ms	4020 KB	number of queries: 10000
67	Incorrect	29 ms	4020 KB	number of queries: 10000
68	Incorrect	33 ms	4020 KB	number of queries: 10000
69	Incorrect	23 ms	4020 KB	number of queries: 10000
70	Incorrect	33 ms	4020 KB	number of queries: 10000
71	Incorrect	49 ms	4020 KB	number of queries: 10000
72	Incorrect	53 ms	4020 KB	number of queries: 10000
73	Incorrect	13 ms	4020 KB	number of queries: 10000
74	Incorrect	29 ms	4020 KB	number of queries: 10000
75	Incorrect	63 ms	4020 KB	number of queries: 10000
76	Incorrect	56 ms	4020 KB	number of queries: 10000
77	Incorrect	36 ms	4020 KB	number of queries: 10000
78	Incorrect	46 ms	4020 KB	number of queries: 10000
79	Incorrect	26 ms	4020 KB	number of queries: 10000
80	Incorrect	33 ms	4020 KB	number of queries: 10000
81	Incorrect	49 ms	4020 KB	number of queries: 10000
82	Incorrect	43 ms	4020 KB	number of queries: 10000
83	Incorrect	56 ms	4020 KB	number of queries: 10000
84	Incorrect	49 ms	4020 KB	number of queries: 10000
85	Incorrect	59 ms	4020 KB	number of queries: 10000
86	Incorrect	39 ms	4020 KB	number of queries: 10000
87	Incorrect	36 ms	4020 KB	number of queries: 10000
88	Incorrect	53 ms	4020 KB	number of queries: 10000
89	Incorrect	29 ms	4020 KB	number of queries: 10000
90	Incorrect	59 ms	4020 KB	number of queries: 10000
91	Incorrect	19 ms	4020 KB	number of queries: 10000
92	Incorrect	49 ms	4020 KB	number of queries: 10000
93	Incorrect	19 ms	4020 KB	number of queries: 10000
94	Incorrect	29 ms	4020 KB	number of queries: 10000
95	Incorrect	73 ms	4020 KB	number of queries: 10000
96	Incorrect	59 ms	4020 KB	number of queries: 10000
97	Incorrect	59 ms	4020 KB	number of queries: 10000

답안 #33296

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 70.0 / 80.0

Subtask #1
20.0 / 20.0

Subtask #2
70.0 / 80.0