oj.uz

Submission #67194

# Submission time Handle Problem Language Result Execution time Memory
67194 2018-08-13T14:20:57 Z radoslav11 The Big Prize (IOI17_prize) C++14
20 / 100
 148 ms 31312 KB 
#include <bits/stdc++.h>
#include "prize.h"
//#include "Lgrader.cpp"
 
using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
 
vector<int> memo[MAXN];
int Q = 0;
bool stop;
bool dummy[MAXN];
 
vector<int> query(int i) 
{
	if(!memo[i].empty()) return memo[i];
	if(stop || dummy[i]) return vector<int>(2, 1e9);
 
	memo[i] = ask(i), Q++;
	if(Q == 10000) assert(false);
	return memo[i];
}
 
int n;
mt19937 mt(42);
 int cnt(int l, int r);
 int cnt1(int l, int r);
 
 
 
int sum(int x) { return query(x)[0]+query(x)[1];}
 int better(int l, int r)
   {
       return sum(l)>sum(r);
   }
  int abetter(int l, int r)
   {
       return sum(l)>=sum(r);
   }
 
int cnt1(int l, int r) { return query(r)[0] - query(l)[0] - better(r,l); }
int cnt(int l, int r) { return query(l)[1] - query(r)[1] - better(l,r); }
 
bool useless(int l, int r)
{
	if(abetter(l, r) && cnt(l,r) <= 0) return true;
	if(abetter(r, l) && cnt1(l,r) <= 0) return true;
	//if(query(r)[0] - query(l)[0] == 0) return true;
	return false;
}
 
void rec(int l, int r)
{
	if(r < l) return;
 
	int mid = (l + r) >> 1;
	if(query(l - 1)[0] + query(l - 1)[1] == 0) stop = 1;	
	if(query(mid)[0] + query(mid)[1] == 0) stop = 1;
	if(query(r + 1)[0] + query(r + 1)[1] == 0) stop = 1;
 
	if(useless(l - 1, r + 1))
	{
		for(int i = l; i <= r; i++)
			memo[i] = query(l - 1);
		return;
	}
  /*
    if(cnt() && )
      {
      for(int i = l; i< mid;i++)dummy[i] = 1;
      for(int i = mid+1; i< r+1;i++)dummy[i] = 1;           return;
      }
   */
   	
  	if(sum(l - 1) == sum(r + 1) && cnt(l - 1, r + 1) == 1 && sum(l) > sum(mid))
    {
      for(int i = l; i <= r; i++)
        if(i != mid) dummy[i] = 1;
      
      return;
    }
  
    if(cnt(l - 1, mid) > cnt(mid, r + 1))
	{
		if(useless(l - 1, mid))
			for(int i = l; i < mid; i++)
				dummy[i] = 1;
		else
			rec(l, mid - 1);
 
		if(useless(mid, r + 1))
			for(int i = mid + 1; i <= r; i++)
				dummy[i] = 1;
		else
			rec(mid + 1, r);	
	}
	else
	{
		if(useless(mid, r + 1))
			for(int i = mid + 1; i <= r; i++)
				dummy[i] = 1;
		else
			rec(mid + 1, r);	
		
		if(useless(l - 1, mid))
			for(int i = l; i < mid; i++)
				dummy[i] = 1;
		else
			rec(l, mid - 1);
 
 
	}
}
 
int find_best(int n) 
{	
	::n = n;
	rec(1, n - 2);stop=	
1;for(int i = 0; i < n; i++)
		if(query(i)[0] + query(i)[1] == 0)
			return i;
 
	return -1;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 25080 KB Output is correct
2 Correct 42 ms 25272 KB Output is correct
3 Correct 46 ms 25272 KB Output is correct
4 Correct 74 ms 31276 KB Output is correct
5 Correct 43 ms 31276 KB Output is correct
6 Correct 28 ms 31276 KB Output is correct
7 Correct 39 ms 31276 KB Output is correct
8 Correct 39 ms 31276 KB Output is correct
9 Correct 42 ms 31276 KB Output is correct
10 Correct 49 ms 31276 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31276 KB Output is correct
2 Correct 37 ms 31276 KB Output is correct
3 Correct 35 ms 31276 KB Output is correct
4 Correct 73 ms 31312 KB Output is correct
5 Correct 36 ms 31312 KB Output is correct
6 Correct 28 ms 31312 KB Output is correct
7 Correct 38 ms 31312 KB Output is correct
8 Correct 44 ms 31312 KB Output is correct
9 Correct 40 ms 31312 KB Output is correct
10 Correct 47 ms 31312 KB Output is correct
11 Correct 50 ms 31312 KB Output is correct
12 Correct 35 ms 31312 KB Output is correct
13 Correct 53 ms 31312 KB Output is correct
14 Correct 39 ms 31312 KB Output is correct
15 Correct 67 ms 31312 KB Output is correct
16 Correct 73 ms 31312 KB Output is correct
17 Partially correct 115 ms 31312 KB Partially correct - number of queries: 6010
18 Correct 86 ms 31312 KB Output is correct
19 Partially correct 78 ms 31312 KB Partially correct - number of queries: 5672
20 Correct 67 ms 31312 KB Output is correct
21 Correct 59 ms 31312 KB Output is correct
22 Correct 54 ms 31312 KB Output is correct
23 Correct 29 ms 31312 KB Output is correct
24 Correct 31 ms 31312 KB Output is correct
25 Correct 50 ms 31312 KB Output is correct
26 Correct 77 ms 31312 KB Output is correct
27 Correct 32 ms 31312 KB Output is correct
28 Correct 70 ms 31312 KB Output is correct
29 Correct 69 ms 31312 KB Output is correct
30 Correct 58 ms 31312 KB Output is correct
31 Partially correct 103 ms 31312 KB Partially correct - number of queries: 5978
32 Correct 45 ms 31312 KB Output is correct
33 Correct 27 ms 31312 KB Output is correct
34 Correct 45 ms 31312 KB Output is correct
35 Correct 45 ms 31312 KB Output is correct
36 Correct 63 ms 31312 KB Output is correct
37 Correct 35 ms 31312 KB Output is correct
38 Correct 30 ms 31312 KB Output is correct
39 Correct 102 ms 31312 KB Output is correct
40 Correct 73 ms 31312 KB Output is correct
41 Correct 69 ms 31312 KB Output is correct
42 Correct 95 ms 31312 KB Output is correct
43 Correct 54 ms 31312 KB Output is correct
44 Correct 54 ms 31312 KB Output is correct
45 Correct 45 ms 31312 KB Output is correct
46 Partially correct 108 ms 31312 KB Partially correct - number of queries: 5993
47 Correct 77 ms 31312 KB Output is correct
48 Correct 43 ms 31312 KB Output is correct
49 Correct 67 ms 31312 KB Output is correct
50 Correct 82 ms 31312 KB Output is correct
51 Correct 53 ms 31312 KB Output is correct
52 Partially correct 92 ms 31312 KB Partially correct - number of queries: 5998
53 Correct 63 ms 31312 KB Output is correct
54 Correct 36 ms 31312 KB Output is correct
55 Partially correct 117 ms 31312 KB Partially correct - number of queries: 5994
56 Correct 58 ms 31312 KB Output is correct
57 Correct 64 ms 31312 KB Output is correct
58 Correct 84 ms 31312 KB Output is correct
59 Correct 81 ms 31312 KB Output is correct
60 Correct 73 ms 31312 KB Output is correct
61 Correct 43 ms 31312 KB Output is correct
62 Correct 31 ms 31312 KB Output is correct
63 Correct 43 ms 31312 KB Output is correct
64 Correct 39 ms 31312 KB Output is correct
65 Correct 45 ms 31312 KB Output is correct
66 Correct 47 ms 31312 KB Output is correct
67 Correct 43 ms 31312 KB Output is correct
68 Correct 27 ms 31312 KB Output is correct
69 Correct 57 ms 31312 KB Output is correct
70 Correct 41 ms 31312 KB Output is correct
71 Partially correct 103 ms 31312 KB Partially correct - number of queries: 8577
72 Correct 36 ms 31312 KB Output is correct
73 Partially correct 123 ms 31312 KB Partially correct - number of queries: 8465
74 Partially correct 101 ms 31312 KB Partially correct - number of queries: 8513
75 Correct 30 ms 31312 KB Output is correct
76 Partially correct 113 ms 31312 KB Partially correct - number of queries: 7425
77 Partially correct 102 ms 31312 KB Partially correct - number of queries: 7703
78 Correct 32 ms 31312 KB Output is correct
79 Correct 57 ms 31312 KB Output is correct
80 Partially correct 148 ms 31312 KB Partially correct - number of queries: 7783
81 Partially correct 139 ms 31312 KB Partially correct - number of queries: 7724
82 Partially correct 121 ms 31312 KB Partially correct - number of queries: 7689
83 Correct 30 ms 31312 KB Output is correct
84 Partially correct 64 ms 31312 KB Partially correct - number of queries: 6349
85 Partially correct 116 ms 31312 KB Partially correct - number of queries: 7872
86 Correct 30 ms 31312 KB Output is correct
87 Incorrect 52 ms 31312 KB Integer -1 violates the range [0, 199999]
88 Halted 0 ms 0 KB -