# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
790695 | 2023-07-23T06:18:15 Z | ttamx | The Big Prize (IOI17_prize) | C++14 | 5 ms | 5072 KB |
#include "prize.h" #include<bits/stdc++.h> using namespace std; const int N=2e5+5; struct fenwick{ int t[N]; void add(int i,int v){ while(i<N)t[i]+=v,i+=i&-i; } int read(int i){ int res=0; while(i>0)res+=t[i],i-=i&=-i; return res; } }f; int cnt=0; int n; int ans=-1; vector<vector<int>> mem(N); vector<int>& ask2(int x){ if(mem[x].empty()){ assert(++cnt<=1e4); mem[x]=ask(x); } return mem[x]; } void bsearch(){ int l=0,r=n-1; while(l<r){ int m=(l+r)/2; auto &res=ask2(m); if(res[0]+res[1]==0)return void(ans=m); if(res[0]){ res[0]--; r=m-1; }else{ res[1]--; l=m+1; } } auto &res=ask2(l); if(res[0]+res[1]==0)return void(ans=l); } int find_best(int _n) { n=_n; int l=0,r=n-1; while(ans==-1)bsearch(); return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4944 KB | Output is correct |
2 | Correct | 3 ms | 4944 KB | Output is correct |
3 | Correct | 4 ms | 5012 KB | Output is correct |
4 | Correct | 2 ms | 5072 KB | Output is correct |
5 | Correct | 5 ms | 4944 KB | Output is correct |
6 | Correct | 3 ms | 5016 KB | Output is correct |
7 | Correct | 2 ms | 5012 KB | Output is correct |
8 | Correct | 3 ms | 5016 KB | Output is correct |
9 | Correct | 2 ms | 5012 KB | Output is correct |
10 | Correct | 2 ms | 4944 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4944 KB | Output is correct |
2 | Correct | 3 ms | 5072 KB | Output is correct |
3 | Correct | 3 ms | 5012 KB | Output is correct |
4 | Correct | 2 ms | 4944 KB | Output is correct |
5 | Correct | 3 ms | 4944 KB | Output is correct |
6 | Correct | 3 ms | 5008 KB | Output is correct |
7 | Correct | 3 ms | 5012 KB | Output is correct |
8 | Correct | 2 ms | 4944 KB | Output is correct |
9 | Correct | 2 ms | 4944 KB | Output is correct |
10 | Correct | 3 ms | 4924 KB | Output is correct |
11 | Incorrect | 4 ms | 4944 KB | answer is not correct |
12 | Halted | 0 ms | 0 KB | - |