Submission #797385

#	Time	Username	Problem	Language	Result	Execution time	Memory
797385		firewater	The Big Prize (IOI17_prize)	C++14	90 / 100	71 ms	2384 KiB

prize

#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 (stderr)

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 / 20
• Subtask 2: 70 / 80