oj.uz

Submission #797385

# Submission time Handle Problem Language Result Execution time Memory
797385 2023-07-29T10:15:53 Z firewater The Big Prize (IOI17_prize) C++14
90 / 100
 71 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>>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;
		}
		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:36:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int mid=l+r>>1;
      |           ~^~
prize.cpp: In member function 'void Tree::add(int, int, int, int)':
prize.cpp:47:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   int mid=l+r>>1;
      |           ~^~
prize.cpp: In member function 'int Tree::asks(int, int, int, int, int)':
prize.cpp:56:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |   int mid=L+R>>1;
      |           ~^~
prize.cpp: In member function 'int Tree::askk(int, int, int, int)':
prize.cpp:64:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |   int mid=l+r>>1;
      |           ~^~
prize.cpp: In function 'int find_best(int)':
prize.cpp:84:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |    mid=l+r+1>>1;
      |        ~~~^~
prize.cpp:102:1: warning: control reaches end of non-void function [-Wreturn-type]
  102 | }
      | ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2256 KB Output is correct
2 Correct 5 ms 2348 KB Output is correct
3 Correct 4 ms 2248 KB Output is correct
4 Correct 7 ms 2336 KB Output is correct
5 Correct 4 ms 2344 KB Output is correct
6 Correct 5 ms 2256 KB Output is correct
7 Correct 5 ms 2352 KB Output is correct
8 Correct 5 ms 2344 KB Output is correct
9 Correct 5 ms 2248 KB Output is correct
10 Correct 5 ms 2256 KB Output is correct

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2332 KB Output is correct
2 Correct 3 ms 2352 KB Output is correct
3 Correct 4 ms 2256 KB Output is correct
4 Correct 3 ms 2348 KB Output is correct
5 Correct 3 ms 2344 KB Output is correct
6 Correct 5 ms 2348 KB Output is correct
7 Correct 6 ms 2336 KB Output is correct
8 Correct 4 ms 2256 KB Output is correct
9 Correct 5 ms 2248 KB Output is correct
10 Correct 5 ms 2256 KB Output is correct
11 Correct 6 ms 2340 KB Output is correct
12 Correct 5 ms 2348 KB Output is correct
13 Correct 6 ms 2248 KB Output is correct
14 Correct 6 ms 464 KB Output is correct
15 Correct 14 ms 2256 KB Output is correct
16 Partially correct 44 ms 2208 KB Partially correct - number of queries: 7282
17 Correct 4 ms 2256 KB Output is correct
18 Partially correct 51 ms 2348 KB Partially correct - number of queries: 8705
19 Correct 6 ms 2316 KB Output is correct
20 Correct 15 ms 1232 KB Output is correct
21 Correct 15 ms 2336 KB Output is correct
22 Correct 8 ms 2216 KB Output is correct
23 Correct 5 ms 2352 KB Output is correct
24 Correct 5 ms 2348 KB Output is correct
25 Correct 27 ms 2336 KB Output is correct
26 Correct 35 ms 2220 KB Output is correct
27 Correct 4 ms 2356 KB Output is correct
28 Partially correct 54 ms 2256 KB Partially correct - number of queries: 8344
29 Partially correct 41 ms 2348 KB Partially correct - number of queries: 6379
30 Partially correct 32 ms 2352 KB Partially correct - number of queries: 8704
31 Correct 6 ms 2212 KB Output is correct
32 Correct 6 ms 2220 KB Output is correct
33 Correct 1 ms 208 KB Output is correct
34 Correct 19 ms 2220 KB Output is correct
35 Correct 7 ms 2248 KB Output is correct
36 Correct 21 ms 2324 KB Output is correct
37 Correct 6 ms 2248 KB Output is correct
38 Correct 5 ms 2228 KB Output is correct
39 Correct 26 ms 2348 KB Output is correct
40 Partially correct 32 ms 2336 KB Partially correct - number of queries: 7564
41 Partially correct 34 ms 2348 KB Partially correct - number of queries: 5265
42 Partially correct 35 ms 2208 KB Partially correct - number of queries: 5265
43 Correct 40 ms 2256 KB Output is correct
44 Correct 30 ms 2332 KB Output is correct
45 Correct 19 ms 2324 KB Output is correct
46 Correct 4 ms 2220 KB Output is correct
47 Correct 26 ms 2384 KB Output is correct
48 Partially correct 33 ms 2336 KB Partially correct - number of queries: 6344
49 Correct 7 ms 2352 KB Output is correct
50 Partially correct 58 ms 2344 KB Partially correct - number of queries: 8773
51 Correct 19 ms 2352 KB Output is correct
52 Correct 6 ms 2248 KB Output is correct
53 Correct 5 ms 2340 KB Output is correct
54 Correct 14 ms 2352 KB Output is correct
55 Correct 6 ms 2248 KB Output is correct
56 Partially correct 61 ms 2344 KB Partially correct - number of queries: 8818
57 Partially correct 50 ms 2256 KB Partially correct - number of queries: 6311
58 Partially correct 49 ms 2248 KB Partially correct - number of queries: 6441
59 Partially correct 35 ms 2336 KB Partially correct - number of queries: 5257
60 Correct 30 ms 2344 KB Output is correct
61 Correct 6 ms 2212 KB Output is correct
62 Correct 4 ms 2384 KB Output is correct
63 Correct 7 ms 2216 KB Output is correct
64 Correct 3 ms 2352 KB Output is correct
65 Correct 8 ms 2332 KB Output is correct
66 Partially correct 41 ms 2336 KB Partially correct - number of queries: 5924
67 Correct 6 ms 2352 KB Output is correct
68 Correct 8 ms 2256 KB Output is correct
69 Partially correct 40 ms 2344 KB Partially correct - number of queries: 5764
70 Correct 9 ms 2332 KB Output is correct
71 Partially correct 71 ms 2256 KB Partially correct - number of queries: 9468
72 Correct 10 ms 2312 KB Output is correct
73 Partially correct 58 ms 2256 KB Partially correct - number of queries: 9335
74 Partially correct 46 ms 2256 KB Partially correct - number of queries: 9392
75 Correct 5 ms 2352 KB Output is correct
76 Partially correct 54 ms 2256 KB Partially correct - number of queries: 8100
77 Partially correct 55 ms 2252 KB Partially correct - number of queries: 8870
78 Correct 9 ms 2256 KB Output is correct
79 Correct 25 ms 2256 KB Output is correct
80 Partially correct 54 ms 2352 KB Partially correct - number of queries: 8847
81 Partially correct 59 ms 2256 KB Partially correct - number of queries: 8897
82 Partially correct 51 ms 2356 KB Partially correct - number of queries: 8839
83 Correct 7 ms 2256 KB Output is correct
84 Partially correct 54 ms 2256 KB Partially correct - number of queries: 7357
85 Partially correct 47 ms 2344 KB Partially correct - number of queries: 8882
86 Partially correct 38 ms 2256 KB Partially correct - number of queries: 6004
87 Correct 8 ms 2256 KB Output is correct
88 Partially correct 34 ms 2256 KB Partially correct - number of queries: 5734
89 Partially correct 37 ms 2256 KB Partially correct - number of queries: 5964
90 Correct 7 ms 2352 KB Output is correct
91 Correct 23 ms 2256 KB Output is correct
92 Partially correct 38 ms 2356 KB Partially correct - number of queries: 5754
93 Partially correct 40 ms 2256 KB Partially correct - number of queries: 6183
94 Partially correct 38 ms 2356 KB Partially correct - number of queries: 6178
95 Partially correct 40 ms 2256 KB Partially correct - number of queries: 6183
96 Partially correct 41 ms 2360 KB Partially correct - number of queries: 6116
97 Partially correct 49 ms 2352 KB Partially correct - number of queries: 5754