Submission #790723

#	Time	Username	Problem	Language	Result	Execution time	Memory
790723		PoonYaPat	The Big Prize (IOI17_prize)	C++14	97.41 / 100	56 ms	5144 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

int mmax=0,n,ans=-1;
vector<int> val[200005];

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
    if (ans!=-1) return;
    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) {
            if (ans!=-1) break;
            Ask(i);
            if (val[i][0]+val[i][1]==0) ans=i;
        }
    } else {
        int mid=(l+r)/2;
        Ask(mid);

        if (val[mid][0]+val[mid][1]!=mmax) {
            if (val[mid][0]+val[mid][1]==0) ans=mid;
            
            for (int i=mid-1; i>l; --i) {
                if (ans!=-1) break;
                Ask(i);
                if (val[i][0]+val[i][1]!=mmax) {
                    if (val[i][0]+val[i][1]==0) ans=i;
                }
                else {
                    solve(l,i);
                    break;
                }
            }

            for (int i=mid+1; i<r; ++i) {
                if (ans!=-1) break;
                Ask(i);
                if (val[i][0]+val[i][1]!=mmax) {
                    if (val[i][0]+val[i][1]==0) ans=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) {
        if (ans!=-1) break;
        Ask(i);
        if (val[i][0]+val[i][1]!=mmax) {
            if (val[i][0]+val[i][1]==0) ans=i;
        }
        else {
            st=i;
            break;
        }
    }

    for (int i=n-1; i>=0; --i) {
        if (ans!=-1) break;
        Ask(i);
        if (val[i][0]+val[i][1]!=mmax) {
            if (val[i][0]+val[i][1]==0) ans=i;
        }
        else {
            ed=i;
            break;
        }
    }

    solve(st,ed);

	return ans;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:93:10: warning: 'ed' may be used uninitialized in this function [-Wmaybe-uninitialized]
   93 |     solve(st,ed);
      |     ~~~~~^~~~~~~
prize.cpp:93:10: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]

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