oj.uz

Submission #33300

# Submission time Handle Problem Language Result Execution time Memory
33300 2017-10-23T09:46:17 Z model_code The Big Prize (IOI17_prize) C++11
97.99 / 100
 43 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 = 5201;
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 13 ms 4020 KB Output is correct
2 Correct 6 ms 4020 KB Output is correct
3 Correct 19 ms 4020 KB Output is correct
4 Correct 23 ms 4020 KB Output is correct
5 Correct 39 ms 4020 KB Output is correct
6 Correct 19 ms 4020 KB Output is correct
7 Correct 16 ms 4020 KB Output is correct
8 Correct 13 ms 4020 KB Output is correct
9 Correct 9 ms 4020 KB Output is correct
10 Correct 16 ms 4020 KB Output is correct

Subtask #2
77.99 / 80.0

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