Submission #1154872

#TimeUsernameProblemLanguageResultExecution timeMemory
1154872modwweThe Big Prize (IOI17_prize)C++20
97.76 / 100
16 ms2484 KiB
//#include "gap.h" //#include "mushrooms.h" #include "prize.h" #pragma GCC optimize("Ofast,unroll-loops") #include<bits/stdc++.h> //#define int long long #define ll long long #define down cout<<'\n'; #define debug cout<<" cucuucucuuu",down #define modwwe int t;cin>>t; while(t--) #define bit(i,j) (i>>j&1) #define sobit(a) __builtin_popcountll(a) #define task2 "ftree" #define task "test" #define fin(x) freopen(x".inp","r",stdin) #define fou(x) freopen(x".out","w",stdout) #define pb push_back #define mask(k) (1<<k) #define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms"; using namespace std; #define getchar_unlocked getchar mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l,int r) { return uniform_int_distribution<int>(l,r)(rd); } void phongbeo(); const int inf = 1e16; const ll mod2 = 1e9+7; const ll base=67; int n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center; int i, s10, s12,k1,k2,k3,s11,lim,w,l,r ; int kk; int t; int el = 19;/* main() { if(fopen(task2".inp","r")) { fin(task2); fou(task2); } if(fopen(task".inp","r")) { fin(task); fou(task); } ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); /// cin>>s1; //int t;cin>>t; while(t--) phongbeo(); // checktime } int prize[200001]; vector<int> ask(int x) { int s=0,ss=0; for(int i=0; i<x; i++) if(prize[i]<prize[x]) s++; for(int i=x+1; i<n; i++) if(prize[i]<prize[x]) ss++; return {s,ss}; }*/ struct st { int t[800001]; void build(int node,int l,int r) { t[node]=r-l+1; if(l==r)return; int mid=l+r>>1; build(node<<1,l,mid); build(node<<1|1,mid+1,r); } void upd(int node,int l,int r,int l1) { t[node]--; if(l==r)return; int mid=l+r>>1; if(l1<=mid)upd(node<<1,l,mid,l1); else upd(node<<1|1,mid+1,r,l1); } int walk(int node,int l,int r,int x) { if(l==r) return l; int mid=l+r>>1; if(t[node<<1]<x)return walk(node<<1|1,mid+1,r,x-t[node<<1]); return walk(node<<1,l,mid,x); } int get(int node,int l,int r,int l1,int r1) { if(l>r1||r<l1) return 0; if(l>=l1&&r<=r1) return t[node]; int mid=l+r>>1; return get(node<<1,l,mid,l1,r1)+get(node<<1|1,mid+1,r,l1,r1); } } st; int dnc(int l,int r,int query,int left,int right) { if(query==0)return -1; s6=st.get(1,0,n-1,l,r); if(s6==0) return -1; s7=st.get(1,0,n-1,1,l-1); s5=st.walk(1,0,n-1,s7+(s6+1)/2); int ngugu=s5; vector<int> a=ask(s5); st.upd(1,0,n-1,s5); if(a[0]+a[1]==0)return s5; if(a[0]+a[1]==s2) { int haha=rand(0,1); if(haha==0){ int x=dnc(l,ngugu-1,a[0]-left,left,a[1]); if(x!=-1) return x; return dnc(ngugu+1,r,a[1]-right,a[0],right); } int x=dnc(ngugu+1,r,a[1]-right,a[0],right); if(x!=-1) return x; return dnc(l,ngugu-1,a[0]-left,left,a[1]); } else { return dnc(l,r,query-1,left,right); } } int find_best(int N) { n=N; s2=0; st.build(1,0,n-1); for(int i=0; i<=474; i++) { vector<int> a=ask(i); if(a[0]+a[1]==0)return i; if(a[0]+a[1]>=s2) { s2=a[0]+a[1]; s3=i; s4=a[1]; s5=a[0]; } st.upd(1,0,n-1,i); } s4+=s3-474; s5=s2-s4; return dnc(475,n-1,s4,s5,0); }/* void phongbeo() { cin>>n; for(int i=0; i<n; i++) prize[i]=2; int x=rand(0,n-1); prize[x]=1; cout<<find_best(n)<<" "<<x; }*/

Compilation message (stderr)

prize.cpp:28:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+16' to '2147483647' [-Woverflow]
   28 | const int inf = 1e16;
      |                 ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...