oj.uz

Submission #33303

# Submission time Handle Problem Language Result Execution time Memory
33303 2017-10-23T09:55:12 Z model_code The Big Prize (IOI17_prize) C++11
99.99 / 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 = 5001;
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 36 ms 4020 KB Output is correct
2 Correct 9 ms 4020 KB Output is correct
3 Correct 13 ms 4020 KB Output is correct
4 Correct 13 ms 4020 KB Output is correct
5 Correct 29 ms 4020 KB Output is correct
6 Correct 13 ms 4020 KB Output is correct
7 Correct 0 ms 4020 KB Output is correct
8 Correct 19 ms 4020 KB Output is correct
9 Correct 53 ms 4020 KB Output is correct
10 Correct 13 ms 4020 KB Output is correct

Subtask #2
79.99 / 80.0

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