Submission #790978

#	Time	Username	Problem	Language	Result	Execution time	Memory
790978		PoonYaPat	The Big Prize (IOI17_prize)	C++14	20 / 100	3056 ms	5364 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;
        }
    }

    Ask(n-1);
    if (val[n-1][0]+val[n-1][1]==0) return n-1;

    int l=0, r=n-1;
    while (l<r) { //find the first lollipop from the left
        int mid=(l+r+1)/2;
        bool can=false;
        for (mid; mid<=r; ++mid) {
            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:75:14: warning: statement has no effect [-Wunused-value]
   75 |         for (mid; mid<=r; ++mid) {
      |              ^~~
prize.cpp:93:1: warning: control reaches end of non-void function [-Wreturn-type]
   93 | }
      | ^
prize.cpp:87:10: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |     solve(st,ed);
      |     ~~~~~^~~~~~~

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