제출 #397209

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

prize

#include "prize.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;

int to;

pair<int, vector<int>> differentRight(int a, vector<int> inf)
{
    int b = to;
    int res = -1;
    vector<int> rinf;
    a++;
    while (a <= b)
    {
        int mid = (a + b) / 2;
        vector<int> cinf = ask(mid);
        if (cinf[0] == 0 && cinf[1] == 0) return {mid, {0, 0}};


        if (cinf[0] == 0)
        {

            vector<int> next = ask(mid + 1);
            return {mid + 1, next};
        }

        if (cinf[1] == 0)
        {
            to = mid - 1;
        }
        if (cinf == inf)
        {
            a = mid + 1;
        } else
        {
            res = mid;
            rinf = cinf;
            b = mid - 1;
        }
    }

    return {res, rinf};
}

int find_best(int N) {
    n = N;
    to = n - 1;
    /*
    if (n <= 5000)
    {
        int res = -1;
        for (int i = 0; i < n; i++)
        {
            vector<int> v = ask(i);
            if (v[0] == 0 && v[1] == 0) res = i;
        }

        return res;
    } */

    vector<int> big = {0, 0};
    vector<int> inf;
    int cur = 0;
    inf = ask(cur);
    big = max(big, inf);

    for (int i = 0; i < 4; i++)
    {
        auto p1 = differentRight(cur, inf);
        cur = p1.first;
        inf = p1.second;
        big = max(big, inf);
    }

    int ca = 0;
    inf = ask(0);
    vector<int> needed = {0, 0};
    while(inf != needed)
    {
        if (inf[0] + inf[1] == big[0] + big[1])
        {
            auto p1 = differentRight(ca, inf);
            ca = p1.first;
            inf = p1.second;
        } else
        {
            ca++;
            inf = ask(ca);
        }
    }



	return ca;
}

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