Submission #797390

#TimeUsernameProblemLanguageResultExecution timeMemory
797390firewaterThe Big Prize (IOI17_prize)C++14
90 / 100
79 ms2384 KiB
#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 (stderr)

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 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...