oj.uz

Submission #757188

# Submission time Handle Problem Language Result Execution time Memory
757188 2023-06-12T18:51:56 Z alexander707070 The Big Prize (IOI17_prize) C++14
0 / 100
 1 ms 428 KB 
#include<bits/stdc++.h>
#include "prize.h"
#define MAXN 200007
using namespace std;
 
int n,r,res;
bool used[MAXN];
vector<int> w;

int solve(int l,int r,int reml,int remr){
    if(l>r)return 0;

    int mid=(l+r)/2,p;
    vector<int> curr;

    while(mid<=r){
        curr=ask(mid);
        if(curr[0]+curr[1]==res)break;
        if(curr[0]+curr[1]==0)return mid;
        mid++;
    }

    if(mid==r+1){
        mid=(l+r)/2-1;
        while(mid>=l){
            curr=ask(mid);
            if(curr[0]+curr[1]==res)break;
            if(curr[0]+curr[1]==0)return mid;
            mid--;
        }

        if(mid==l-1)return 0;

        curr[0]-=reml;
        if(curr[0]>0){
            return solve(l,mid-1,reml,remr+(r-mid));
        }
        return 0;

    }else{
        curr[0]-=reml-(mid-(l+r)/2);
        curr[1]-=remr;

        if(curr[0]>0){
            p=solve(l,(l+r)/2-1,reml,remr+curr[1]+(mid-(l+r)/2));
            if(p!=0)return p;
        }
        if(curr[1]>0){
            p=solve(mid+1,r,reml+curr[0],remr);
            if(p!=0)return p;
        }

        return 0;
    }

    return 0;
}

int find_best(int N){
    N=n;
    for(int i=1;i<=10;i++){
        r=rand()%n+1; w=ask(r);
        res=max(res,w[0]+w[1]);
    }

    return solve(1,n,0,0);
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 336 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 428 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -