제출 #262747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
262747		Coroian_David	커다란 상품 (IOI17_prize)	C++11	20 / 100	99 ms	1244 KiB

prize

#include <bits/stdc++.h>

//#include "prize.h"

#define MAX_N 200000

using namespace std;

typedef long long lint;

vector<int> ask(int i);

int N;
int mx;
int rez = -1;
int spec[MAX_N + 1];

vector <int> doAsk(int poz)
{
    if(rez != -1)
        return {0, 0};

    vector <int> a = ask(poz - 1);

    if(a[0] + a[1] == 0)
        rez = poz;

    return a;
}

int px;
int cst, cdr;

bool verif(int poz)
{
    if(rez != -1)
        return 0;

    vector <int> a = doAsk(poz);

    if(a[0] + a[1] == mx)
    {
        cst = a[0];
        cdr = a[1];
        px = poz;

        return 1;
    }

    spec[poz] = 1;
    return 0;
}

void intreaba(int poz)
{
    int n = N;

    if(rez != -1)
        return;

    if(verif(poz))
        return;

    int st = poz - 1;
    int dr = poz + 1;
    while(st >= 1 || dr <= n)
    {
        if(st >= 1)
        {
            if(verif(st))
                return;

            st --;
        }

        if(dr <= n)
        {
            if(verif(dr))
                return;

            dr ++;
        }
    }
}

void divide(int st, int dr, int pst, int pdr, int cate)
{
    if(rez != -1)
        return;

    if(st > dr || cate == 0)
        return;

    //cout << " SUNTEM " << st << " " << dr << " AVEM INSRE ST " << pst << " DR " << pdr << " " << cate << "\n";

    if((dr - st + 1) - cate <= 2)
    {
        for(int i = st; i <= dr; i ++)
        {
            spec[i] = 1;
            doAsk(i);
        }

        return;
    }



    int mid = (st + dr) >> 1;
    intreaba(mid);

    divide(st, px - 1, pst, cdr, cst - pst);
    divide(px + 1, dr, cst, pdr, cdr - pdr);
}

int find_best(int n)
{
    N = n;

    if(n <= 5000)
    {
        for(int i = 0; i < n; i ++)
        {
            vector<int> a = ask(i);

            if(a[0] + a[1] == 0)
                return i;
        }

        assert(1 == 0);
        //return;
    }

    srand(time(0));
    for(int i = 1; i <= 10; i ++)
    {
        lint poz = 1LL * rand() * rand() % n;

        vector <int> a = ask(poz);

        if(a[0] + a[1] == 0)
            return poz;

        mx = max(mx, a[0] + a[1]);
    }

    divide(1, n, 0, 0, mx);

    return rez - 1;
}

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