Submission #986138

#	Time	Username	Problem	Language	Result	Execution time	Memory
986138		AlphaMale06	The Big Prize (IOI17_prize)	C++14	100 / 100	39 ms	11904 KiB

prize

#include <bits/stdc++.h>

#include "prize.h"

using namespace std;
using ll = long long;

vector<int> ask(int i);

vector<int> a[200006];
int summ = 0;

int solve(int l, int r){
    if(l+1>=r)return 0;
    int cnt = a[l][1]-a[r][1];
    if(cnt==0)return 0;
    int s = l+r>>1;
    if(a[s][0]==-1)a[s]=ask(s);
    if(a[s][0]+a[s][1]==summ)return max(solve(l, s), solve(s, r));
    if(a[s][0]+a[s][1]==0)return s;
    int R = s-1, L = s+1;
    for(int i=s-1; i>=l; i--){
        if(a[i][0]==-1)a[i]=ask(i);
        if(a[i][0]+a[i][1]==0)return i;
        if(a[i][0]+a[i][1]==summ){
            R=i;
            break;
        }
    }
    for(int i=s+1; i<=r; i++){
        if(a[i][0]==-1)a[i]=ask(i);
        if(a[i][0]+a[i][1]==0)return i;
        if(a[i][0]+a[i][1]==summ){
            L=i;
            break;
        }
    }
    return max(solve(l, R), solve(L, r));
}

int find_best(int n){
	if(n<=5000){
        for(int i=0; i<n; i++){
            vector<int> ans = ask(i);
            if(ans[0]==0 && ans[1]==0)return i;
        }
	}
	for(int i=0; i< n; i++){
        a[i].push_back(-1);
	}
	int L = -1, R = -1;
    vector<int> indices;
    for(int i=0; i<30; i++){
        a[i]=ask(i);
        if(a[i][0]+a[i][1]==0)return i;
        summ=max(summ, a[i][0]+a[i][1]);
    }
    for(int i=n-1; i>=n-30; i--){
        a[i]=ask(i);
        if(a[i][0]+a[i][1]==0)return i;
        summ=max(summ, a[i][0]+a[i][1]);
    }

    for(int i=30; i<n-473; i+=475){
        indices.push_back(i);
        a[i]=ask(i);
        if(a[i][0]+a[i][1]==0)return i;
        summ=max(summ, a[i][0]+a[i][1]);
    }
    indices.push_back(n-30);
    for(int i=0; i<indices.size()-1; i++){
        int x = indices[i];
        while(a[x][0]+a[x][1]!=summ){
            x++;
            a[x]=ask(x);
            if(a[x][0]+a[x][1]==0)return x;
        }
        indices[i]=x;
    }
    int ans = 0;
    for(int i=0; i<indices.size()-1; i++){
        ans=max(ans, solve(indices[i], indices[i+1]));
    }
    return ans;
}

Compilation message (stderr)

prize.cpp: In function 'int solve(int, int)':
prize.cpp:17:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |     int s = l+r>>1;
      |             ~^~
prize.cpp: In function 'int find_best(int)':
prize.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i=0; i<indices.size()-1; i++){
      |                  ~^~~~~~~~~~~~~~~~~
prize.cpp:81:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i=0; i<indices.size()-1; i++){
      |                  ~^~~~~~~~~~~~~~~~~
prize.cpp:51:6: warning: unused variable 'L' [-Wunused-variable]
   51 |  int L = -1, R = -1;
      |      ^
prize.cpp:51:14: warning: unused variable 'R' [-Wunused-variable]
   51 |  int L = -1, R = -1;
      |              ^

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