Submission #790891

#	Time	Username	Problem	Language	Result	Execution time	Memory
790891		PoonYaPat	The Big Prize (IOI17_prize)	C++14	0 / 100	12 ms	9880 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
 
int mmax=0,n,non_lol;
vector<int> val[200005];
vector<int> none;
 
void Ask(int x) {
    if (!val[x].size()) val[x]=ask(x);
}
 
void solve(int l, int r) { //l and r must be lolli_pop
    Ask(l);
    Ask(r);
    if (val[r][0]==val[l][0]) return;
    if (val[r][0]-val[l][0]==r-l-1) {
        for (int i=l+1; i<r; ++i) none.push_back(i);
    } else {
        int mid=(l+r)/2;
        Ask(mid);
 
        if (val[mid][0]+val[mid][1]!=mmax) {
            none.push_back(mid);
            
            for (int i=mid-1; i>l; --i) {
                Ask(i);
                if (val[i][0]+val[i][1]!=mmax) none.push_back(i);
                else {
                    solve(l,i);
                    break;
                }
            }
 
            for (int i=mid+1; i<r; ++i) {
                Ask(i);
                if (val[i][0]+val[i][1]!=mmax) none.push_back(i);
                else {
                    solve(i,r);
                    break;
                }
            }
 
        } else {
            solve(l,mid);
            solve(mid,r);
        }
    }
 
}
 
int find_best(int N) {
	n=N;
	for (int i=0; i<min(500,n); ++i) {
		val[i]=ask(i);
		mmax=max(mmax,val[i][0]+val[i][1]);
	}
    int st,ed;
    for (int i=0; i<n; ++i) {
        Ask(i);
        if (val[i][0]+val[i][1]!=mmax) none.push_back(i);
        else {
            st=i;
            break;
        }
    }

    int l=0, r=n-1;
    while (l<r) {
        int mid=(l+r+1)/2;
        bool can=false;
        for (int i=mid; i<=r; ++i) {
            Ask(mid);
            if (val[mid][0]+val[mid][1]==mmax) {
                can=true;
                break;
            }
        }
        if (can) l=mid;
        else r=mid-1;
    }
    ed=l;
 
    solve(st,ed);
 
	for (auto s : none) {
		Ask(s);
		if (val[s][0]+val[s][1]==0) return s;
	}
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:90:1: warning: control reaches end of non-void function [-Wreturn-type]
   90 | }
      | ^
prize.cpp:84:10: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |     solve(st,ed);
      |     ~~~~~^~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80