oj.uz

Submission #33302

# Submission time Handle Problem Language Result Execution time Memory
33302 2017-10-23T09:52:35 Z model_code The Big Prize (IOI17_prize) C++11
90 / 100
 53 ms 4020 KB 
#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 = 6000;
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

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4020 KB Output is correct
2 Correct 19 ms 4020 KB Output is correct
3 Correct 29 ms 4020 KB Output is correct
4 Correct 16 ms 4020 KB Output is correct
5 Correct 19 ms 4020 KB Output is correct
6 Correct 39 ms 4020 KB Output is correct
7 Correct 23 ms 4020 KB Output is correct
8 Correct 53 ms 4020 KB Output is correct
9 Correct 26 ms 4020 KB Output is correct
10 Correct 26 ms 4020 KB Output is correct

Subtask #2
70.0 / 80.0

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