제출 #103372

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103372		daniel920712	커다란 상품 (IOI17_prize)	C++14	90 / 100	62 ms	2048 KiB

prize

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <assert.h>
#include "prize.h"

using namespace std;
int all[200005];
int l[200005],r[200005];
int ans=0;
int F(int L,int R,int here)
{
    //printf("%d %d\n",L,R);
    vector < int > t;
    int x;
    if(l[(L+R)/2]==-1)
    {
        ans++;
        assert(ans<=10000);
        t=ask((L+R)/2);
        l[(L+R)/2]=t[0];
        r[(L+R)/2]=t[1];
    }
    if(l[R]==-1)
    {
        ans++;
        assert(ans<=10000);
        t=ask(R);
        l[R]=t[0];
        r[R]=t[1];
    }
    if(l[L]==-1)
    {
        ans++;
        assert(ans<=10000);
        t=ask(L);
        l[L]=t[0];
        r[L]=t[1];
    }
    if(l[L]==0&&r[L]==0) return L;
    if(l[R]==0&&r[R]==0) return R;
    if(l[(L+R)/2]==0&&r[(L+R)/2]==0) return (L+R)/2;
    if(L==R)
    {

        if(l[L]||r[L]) return -1;
        return L;
    }
    else if(L+1==R)
    {

        if(l[L]||r[L])
        {
            if(l[R]||r[R]) return -1;
            return R;
        }
        return L;
    }
    else
    {
        //printf("%d %d %d %d %d %d\n",l[L],r[L],l[(L+R)/2],r)
        if(r[R]==r[(L+R)/2]) return F(L,(L+R)/2,here);
        else if(l[L]==l[(L+R)/2]) return F((L+R)/2+1,R,here);
        else if(here%2==0)
        {
            x=F((L+R)/2+1,R,1-here);
            if(x!=-1) return x;
            return F(L,(L+R)/2,1-here);
        }
        else 
        {
            x=F(L,(L+R)/2+1,1-here);
            if(x!=-1) return x;
            return F((L+R)/2+1,R,1-here);
        }
    }
}
int find_best(int n)
{
    vector < int > t;
    int i,j,all=0;
    for(i=0;i<n;i++) l[i]=r[i]=-1;

    ans++;
    assert(ans<=10000);
    t=ask(0);
    l[0]=t[0];
    r[0]=t[1];

    ans++;
    assert(ans<=10000);
    t=ask(n-1);
    l[n-1]=t[0];
    r[n-1]=t[1];
    return F(0,n-1,0);
}

컴파일 시 표준 에러 (stderr) 메시지

prize.cpp: In function 'int find_best(int)':
prize.cpp:81:11: warning: unused variable 'j' [-Wunused-variable]
     int i,j,all=0;
           ^
prize.cpp:81:13: warning: unused variable 'all' [-Wunused-variable]
     int i,j,all=0;
             ^~~

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