Submission #903608

#	Time	Username	Problem	Language	Result	Execution time	Memory
903608		JakobZorz	The Big Prize (IOI17_prize)	C++17	97.71 / 100	29 ms	3040 KiB

prize

#include"prize.h"
#include<iostream>
#include<vector>
#include<set>
using namespace std;

bool dpt[200000];
pair<int,int>dp[200000];
int n;
bool found;

void query(int i){
    if(dpt[i])
        return;
    dpt[i]=true;
    auto res=ask(i);
    dp[i]={res[0],res[1]};
    if(res[0]+res[1]==0){
        found=true;
        return;
    }
    int c=i+1;
    while(c<n){
        if(dpt[c]){
            if(dp[c]==dp[i]){
                for(int j=i+1;j<c;j++){
                    dp[j]=dp[i];
                    dpt[j]=true;
                }
            }
            break;
        }
        c++;
    }
    
    c=i-1;
    while(c>=0){
        if(dpt[c]){
            if(dp[c]==dp[i]){
                for(int j=c+1;j<i;j++){
                    dp[j]=dp[i];
                    dpt[j]=true;
                }
            }
            break;
        }
        c--;
    }
}

void fo(int l,int r){
    if(l>=r)
        return;
    int m=(l+r)/2;
    if(found)
        return;
    query(m);
    
    if(l<r-1){
        if(dp[m].first>dp[m].second){
            fo(l,m);
            fo(m,r);
        }else{
            fo(m,r);
            fo(l,m);
        }
    }
}

int find_best(int N){
    n=N;
    fo(0,n);
    
    for(int i=0;i<n;i++)
        if(dpt[i]&&dp[i].first+dp[i].second==0)
            return i;
    
	return -1;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:74:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   74 |     for(int i=0;i<n;i++)
      |     ^~~
prize.cpp:78:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   78 |  return -1;
      |  ^~~~~~

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