| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 339616 | ogibogi2004 | The Big Prize (IOI17_prize) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "prize.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#include<bits/stdc++.h>
const int MAXN=2e5+6;
pair<int,int> answer[MAXN];
vector<int>valuable;
int maxs=0;
pair<int,int>q;
vector<int>lollipops;
char lorv[MAXN];
pair<int,int> get_answer(int i)
{
if(answer[i].first!=-1)return answer[i];
vector<int>q=ask(i);
answer[i].first=q[0];
answer[i].second=q[1];
return answer[i];
}
void bs(int l,int r)
{
if(r>l)return;
pair<int,int> ivan=get_answer(l);
if(l==r)
{
if(ivan.first+ivan.second!=maxs)
{
valuable.push_back(l);
}
return;
}
if(ivan.first+ivan.second!=maxs)
{
valuable.push_back(l);
bs(l+1,r);
return;
}
int mid,low=l,high=r,ans=-1;
while(low<=high)
{
mid=(low+high)/2;
ivan=get_answer(mid);
if(ivan.first+ivan.second!=maxs)
{
ans=mid;
break;
}
if(ivan.first>get_answer(l).first)
{
mid=high-1;
}
else low=mid+1;
}
if(ans==-1)return;
valuable.push_back(ans);
bs(l+1,ans-1);
bs(ans+1,r);
}
int find_best(int n) {
/*for(int i = 0; i < n; i++) {
std::vector<int> res = ask(i);
if(res[0] + res[1] == 0)
return i;
}
return 0;*/
if(n<=5000)
{
for(int i=0;i<n;i++)
{
vector<int>t=ask(i);
if(t[0]+t[1]==0)
{
return i;
}
}
}
for(int i=0;i<n;i++)answer[i]={-1,-1};
for(int i=0;i<480;i++)
{
q=get_answer(i);
if(q.first+q.second==0)
{
return i;
}
answer[i]=q;
maxs=max(maxs,q.first+q.second);
}
for(int i=0;i<n;i++)lorv[i]='?';
for(int i=0;i<480;i++)
{
if(answer[i].first+answer[i].second==maxs)
{
lorv[i]='L';
lollipops.push_back(i);
}
else
{
lorv[i]='V';
valuable.push_back(i);
}
}
bs(480,n-1);
for(auto j:valuable)
{
if(get_answer(j).first+get_answer(j).second==0)
{
return j;
}
}
}
static const int max_q = 10000;
static int n;
static int query_count = 0;
static vector<int> g;
static vector<vector<int> > rank_count;
vector<int> ask(int i) {
query_count++;
if(query_count > max_q) {
cerr << "Query limit exceeded" << endl;
exit(0);
}
if(i < 0 || i >= n) {
cerr << "Bad index: " << i << endl;
exit(0);
}
vector<int> res(2);
res[0] = rank_count[g[i] - 1][i + 1];
res[1] = rank_count[g[i] - 1][n] - res[0];
return res;
}
int main() {
cin >> n;
g.resize(n);
for(int i = 0; i < n; i++) {
cin >> g[i];
if(g[i] < 1) {
cerr << "Invalid rank " << g[i] << " at index " << i << endl;
exit(0);
}
}
int max_rank = *max_element(g.begin(), g.end());
rank_count.resize(max_rank + 1, vector<int>(n + 1, 0));
for(int r = 0; r <= max_rank; r++) {
for(int i = 1; i <= n; i++) {
rank_count[r][i] = rank_count[r][i - 1];
if(g[i - 1] == r)
rank_count[r][i]++;
}
}
for(int i = 0; i <= n; i++)
for(int r = 1; r <= max_rank; r++)
rank_count[r][i] += rank_count[r - 1][i];
int res = find_best(n);
cout << res << endl << "Query count: " << query_count << endl;
return 0;
}