oj.uz

Submission #797390

# Submission time Handle Problem Language Result Execution time Memory
797390 2023-07-29T10:17:11 Z firewater The Big Prize (IOI17_prize) C++14
90 / 100
 79 ms 2384 KB 
#include "prize.h"
#include <vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;









#define MX 202300
int n,m,l,r,mx,mid,x;
vector<int>c;
struct Tree
{
	#define ls x*2
	#define rs x*2+1
	int s[MX<<2];
	void push_up(int x)
	{
		s[x]=s[ls]+s[rs];
		return;
	}
	void build(int x,int l,int r)
	{
		s[x]=0;
		if(l==r)return;
		int mid=l+r>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		return;
	}
	void add(int x,int l,int r,int y)
	{
		if(l==r){
			s[x]++;
			return;
		}
		int mid=l+r>>1;
		if(y<=mid)add(ls,l,mid,y);
		else add(rs,mid+1,r,y);
		push_up(x);
		return;
	}
	int asks(int x,int L,int R,int l,int r)
	{
		if(L==l&&R==r)return s[x];
		int mid=L+R>>1;
		if(r<=mid)return asks(ls,L,mid,l,r);
		else if(l>mid)return asks(rs,mid+1,R,l,r);
		else return asks(ls,L,mid,l,mid)+asks(rs,mid+1,R,mid+1,r);
	}
	int askk(int x,int l,int r,int k)
	{
		if(l==r)return l;
		int mid=l+r>>1;
		if(mid-l+1-s[ls]>=k)return askk(ls,l,mid,k);
		else return askk(rs,mid+1,r,k-(mid-l+1-s[ls]));
	}
}T;
int find_best(int N) {
	n=N;
	mx=0;
	for(int i=1;i<=min(500,n);++i){
		c=ask(i-1);
		mx=max(mx,c[0]+c[1]);
		// printf("%d %d %d\n",i,c[0],c[1]);
	}
	m=n;
	T.build(1,1,n);
	while(1<=m){
		l=1;r=m;
		// printf("%d %d\n",l,r);
		while(l<r){
			// printf("%d %d\n",l,r);
			mid=l+r>>1;
			x=T.askk(1,1,n,mid);
			c=ask(x-1);
			if(c[0]+c[1]!=mx){
				l=mid;
				break;
			}
			// printf("%d %d %d %d %d %d\n",l,r,mid,x,c[0],T.asks(1,1,n,1,x-1));
			if(c[0]>T.asks(1,1,n,1,x-1))r=mid-1;
			else l=mid+1;
		}
		x=T.askk(1,1,n,l);
		c=ask(x-1);
		// printf("%d %d %d\n",x,c[0],c[1]);
		if(c[0]+c[1]==0)return x-1;
		T.add(1,1,n,x);
		m--;
	}
}

Compilation message

prize.cpp: In member function 'void Tree::build(int, int, int)':
prize.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int mid=l+r>>1;
      |           ~^~
prize.cpp: In member function 'void Tree::add(int, int, int, int)':
prize.cpp:46:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   int mid=l+r>>1;
      |           ~^~
prize.cpp: In member function 'int Tree::asks(int, int, int, int, int)':
prize.cpp:55:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |   int mid=L+R>>1;
      |           ~^~
prize.cpp: In member function 'int Tree::askk(int, int, int, int)':
prize.cpp:63:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |   int mid=l+r>>1;
      |           ~^~
prize.cpp: In function 'int find_best(int)':
prize.cpp:83:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |    mid=l+r>>1;
      |        ~^~
prize.cpp:101:1: warning: control reaches end of non-void function [-Wreturn-type]
  101 | }
      | ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2360 KB Output is correct
2 Correct 6 ms 2332 KB Output is correct
3 Correct 5 ms 2356 KB Output is correct
4 Correct 4 ms 2296 KB Output is correct
5 Correct 6 ms 2348 KB Output is correct
6 Correct 6 ms 2216 KB Output is correct
7 Correct 6 ms 2256 KB Output is correct
8 Correct 4 ms 2344 KB Output is correct
9 Correct 4 ms 2216 KB Output is correct
10 Correct 5 ms 2352 KB Output is correct

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2208 KB Output is correct
2 Correct 5 ms 2344 KB Output is correct
3 Correct 5 ms 2348 KB Output is correct
4 Correct 5 ms 2344 KB Output is correct
5 Correct 4 ms 2248 KB Output is correct
6 Correct 5 ms 2220 KB Output is correct
7 Correct 5 ms 2352 KB Output is correct
8 Correct 6 ms 2348 KB Output is correct
9 Correct 5 ms 2216 KB Output is correct
10 Correct 6 ms 2256 KB Output is correct
11 Correct 9 ms 2344 KB Output is correct
12 Correct 5 ms 2208 KB Output is correct
13 Correct 10 ms 2344 KB Output is correct
14 Correct 8 ms 464 KB Output is correct
15 Correct 14 ms 2352 KB Output is correct
16 Partially correct 40 ms 2212 KB Partially correct - number of queries: 7273
17 Correct 4 ms 2320 KB Output is correct
18 Partially correct 48 ms 2216 KB Partially correct - number of queries: 8657
19 Correct 4 ms 2272 KB Output is correct
20 Correct 18 ms 1232 KB Output is correct
21 Correct 31 ms 2348 KB Output is correct
22 Correct 8 ms 2344 KB Output is correct
23 Correct 5 ms 2208 KB Output is correct
24 Correct 4 ms 2344 KB Output is correct
25 Correct 29 ms 2208 KB Output is correct
26 Correct 37 ms 2356 KB Output is correct
27 Correct 6 ms 2216 KB Output is correct
28 Partially correct 52 ms 2324 KB Partially correct - number of queries: 8196
29 Partially correct 42 ms 2224 KB Partially correct - number of queries: 6277
30 Partially correct 72 ms 2352 KB Partially correct - number of queries: 8571
31 Correct 5 ms 2348 KB Output is correct
32 Correct 7 ms 2324 KB Output is correct
33 Correct 1 ms 208 KB Output is correct
34 Correct 21 ms 2352 KB Output is correct
35 Correct 7 ms 2340 KB Output is correct
36 Correct 21 ms 2340 KB Output is correct
37 Correct 7 ms 2340 KB Output is correct
38 Correct 5 ms 2248 KB Output is correct
39 Correct 28 ms 2340 KB Output is correct
40 Partially correct 65 ms 2344 KB Partially correct - number of queries: 7359
41 Partially correct 32 ms 2212 KB Partially correct - number of queries: 5115
42 Partially correct 35 ms 2216 KB Partially correct - number of queries: 5115
43 Correct 33 ms 2348 KB Output is correct
44 Correct 25 ms 2332 KB Output is correct
45 Correct 23 ms 2212 KB Output is correct
46 Correct 5 ms 2360 KB Output is correct
47 Correct 37 ms 2344 KB Output is correct
48 Partially correct 44 ms 2212 KB Partially correct - number of queries: 6296
49 Correct 12 ms 2352 KB Output is correct
50 Partially correct 69 ms 2348 KB Partially correct - number of queries: 8666
51 Correct 34 ms 2216 KB Output is correct
52 Correct 6 ms 2256 KB Output is correct
53 Correct 5 ms 2336 KB Output is correct
54 Correct 31 ms 2344 KB Output is correct
55 Correct 6 ms 2248 KB Output is correct
56 Partially correct 68 ms 2256 KB Partially correct - number of queries: 8685
57 Partially correct 49 ms 2360 KB Partially correct - number of queries: 6214
58 Partially correct 45 ms 2332 KB Partially correct - number of queries: 6311
59 Partially correct 41 ms 2352 KB Partially correct - number of queries: 5110
60 Correct 37 ms 2256 KB Output is correct
61 Correct 5 ms 2256 KB Output is correct
62 Correct 5 ms 2348 KB Output is correct
63 Correct 5 ms 2208 KB Output is correct
64 Correct 5 ms 2256 KB Output is correct
65 Correct 10 ms 2348 KB Output is correct
66 Partially correct 46 ms 2208 KB Partially correct - number of queries: 5924
67 Correct 10 ms 2308 KB Output is correct
68 Correct 10 ms 2332 KB Output is correct
69 Partially correct 33 ms 2332 KB Partially correct - number of queries: 5764
70 Correct 11 ms 2344 KB Output is correct
71 Partially correct 79 ms 2256 KB Partially correct - number of queries: 8996
72 Correct 11 ms 2360 KB Output is correct
73 Partially correct 75 ms 2352 KB Partially correct - number of queries: 8870
74 Partially correct 68 ms 2360 KB Partially correct - number of queries: 8924
75 Correct 8 ms 2256 KB Output is correct
76 Partially correct 54 ms 2272 KB Partially correct - number of queries: 7700
77 Partially correct 69 ms 2256 KB Partially correct - number of queries: 8679
78 Correct 8 ms 2360 KB Output is correct
79 Correct 24 ms 2256 KB Output is correct
80 Partially correct 79 ms 2356 KB Partially correct - number of queries: 8692
81 Partially correct 75 ms 2256 KB Partially correct - number of queries: 8679
82 Partially correct 60 ms 2344 KB Partially correct - number of queries: 8615
83 Correct 5 ms 2256 KB Output is correct
84 Partially correct 48 ms 2336 KB Partially correct - number of queries: 7146
85 Partially correct 48 ms 2256 KB Partially correct - number of queries: 8691
86 Partially correct 49 ms 2360 KB Partially correct - number of queries: 5995
87 Correct 8 ms 2356 KB Output is correct
88 Partially correct 41 ms 2344 KB Partially correct - number of queries: 5725
89 Partially correct 38 ms 2256 KB Partially correct - number of queries: 5955
90 Correct 6 ms 2256 KB Output is correct
91 Correct 31 ms 2352 KB Output is correct
92 Partially correct 42 ms 2304 KB Partially correct - number of queries: 5745
93 Partially correct 42 ms 2384 KB Partially correct - number of queries: 6164
94 Partially correct 53 ms 2256 KB Partially correct - number of queries: 6181
95 Partially correct 40 ms 2216 KB Partially correct - number of queries: 6146
96 Partially correct 38 ms 2256 KB Partially correct - number of queries: 6104
97 Partially correct 49 ms 2360 KB Partially correct - number of queries: 5745