제출 #265085

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
265085		arayi	커다란 상품 (IOI17_prize)	C++17	0 / 100	48 ms	2984 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;


const int N = 2e5 + 55;
int dz[N], aj[N];
bool col[N];
int mx, q;
int as(int a)
{
    q++;
    if(q == 5000)
    {
        assert(0);
    }
    vector <int> fp = ask(a);
    if(fp[0] + fp[1] == 0) return 0;
    if(!col[a] && (fp[0] + fp[1]) * (fp[0] + fp[1]) < mx) return 2;
    if(fp[0] - dz[a]) return -1;
    return 1;
}

int find_best(int n) {
    mx = (n + 1) / 2;
    while(true)
    {
        int l = 0, r = n - 1;
        while(l <= r)
        {
            int mid = (l + r)/2;
            int sm = as(mid);
            if(sm == 0) return mid;
            if(sm == 2)
            {
                for (int i = mid + 1; i < n; i++)
                    dz[i]++;
                for (int i = mid - 1; i >= 0; i--)
                    aj[i]++;
                col[mid] = true;
                break;
            }
            if(sm == 1) l = mid + 1;
            if(sm == -1) r = mid - 1;
        }
    }
}

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