답안 #67189 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67189	2018-08-13T14:05:06 Z	radoslav11	커다란 상품 (IOI17_prize)	C++14	20 / 100	117 ms	31420 KB

prize

#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);
 
 
bool useless(int l, int r)
{
	if(cnt(l,r) <= 0) return true;
	if(cnt1(l,r) <= 0) return true;
	//if(query(r)[0] - query(l)[0] == 0) return true;
	return false;
}
int sum(int x) { return query(x)[0]+query(x)[1];}
 int better(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); }
 
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(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(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

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	25128 KB	Output is correct
2	Correct	43 ms	25148 KB	Output is correct
3	Correct	45 ms	25220 KB	Output is correct
4	Correct	77 ms	31228 KB	Output is correct
5	Correct	42 ms	31228 KB	Output is correct
6	Correct	43 ms	31348 KB	Output is correct
7	Correct	38 ms	31348 KB	Output is correct
8	Correct	41 ms	31348 KB	Output is correct
9	Correct	35 ms	31348 KB	Output is correct
10	Correct	49 ms	31348 KB	Output is correct

Subtask #2
0 / 80.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	31348 KB	Output is correct
2	Correct	39 ms	31348 KB	Output is correct
3	Correct	36 ms	31348 KB	Output is correct
4	Correct	68 ms	31416 KB	Output is correct
5	Correct	38 ms	31416 KB	Output is correct
6	Correct	42 ms	31420 KB	Output is correct
7	Correct	40 ms	31420 KB	Output is correct
8	Correct	39 ms	31420 KB	Output is correct
9	Correct	33 ms	31420 KB	Output is correct
10	Correct	53 ms	31420 KB	Output is correct
11	Correct	36 ms	31420 KB	Output is correct
12	Correct	35 ms	31420 KB	Output is correct
13	Correct	55 ms	31420 KB	Output is correct
14	Correct	39 ms	31420 KB	Output is correct
15	Correct	107 ms	31420 KB	Output is correct
16	Correct	117 ms	31420 KB	Output is correct
17	Correct	83 ms	31420 KB	Output is correct
18	Correct	110 ms	31420 KB	Output is correct
19	Correct	90 ms	31420 KB	Output is correct
20	Correct	63 ms	31420 KB	Output is correct
21	Correct	100 ms	31420 KB	Output is correct
22	Correct	73 ms	31420 KB	Output is correct
23	Correct	32 ms	31420 KB	Output is correct
24	Correct	36 ms	31420 KB	Output is correct
25	Correct	106 ms	31420 KB	Output is correct
26	Correct	67 ms	31420 KB	Output is correct
27	Correct	33 ms	31420 KB	Output is correct
28	Correct	106 ms	31420 KB	Output is correct
29	Correct	83 ms	31420 KB	Output is correct
30	Correct	95 ms	31420 KB	Output is correct
31	Correct	77 ms	31420 KB	Output is correct
32	Correct	46 ms	31420 KB	Output is correct
33	Correct	24 ms	31420 KB	Output is correct
34	Correct	65 ms	31420 KB	Output is correct
35	Correct	42 ms	31420 KB	Output is correct
36	Correct	87 ms	31420 KB	Output is correct
37	Correct	40 ms	31420 KB	Output is correct
38	Correct	30 ms	31420 KB	Output is correct
39	Correct	77 ms	31420 KB	Output is correct
40	Correct	99 ms	31420 KB	Output is correct
41	Correct	89 ms	31420 KB	Output is correct
42	Correct	84 ms	31420 KB	Output is correct
43	Correct	101 ms	31420 KB	Output is correct
44	Correct	74 ms	31420 KB	Output is correct
45	Correct	94 ms	31420 KB	Output is correct
46	Correct	72 ms	31420 KB	Output is correct
47	Correct	79 ms	31420 KB	Output is correct
48	Correct	82 ms	31420 KB	Output is correct
49	Correct	98 ms	31420 KB	Output is correct
50	Correct	110 ms	31420 KB	Output is correct
51	Correct	64 ms	31420 KB	Output is correct
52	Correct	63 ms	31420 KB	Output is correct
53	Correct	47 ms	31420 KB	Output is correct
54	Correct	113 ms	31420 KB	Output is correct
55	Correct	81 ms	31420 KB	Output is correct
56	Correct	96 ms	31420 KB	Output is correct
57	Correct	95 ms	31420 KB	Output is correct
58	Incorrect	91 ms	31420 KB	Integer -1 violates the range [0, 199999]
59	Halted	0 ms	0 KB	-

답안 #67189

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 0 / 80.0

Subtask #1
20.0 / 20.0

Subtask #2
0 / 80.0