제출 #1019742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1019742		andrei_iorgulescu	커다란 상품 (IOI17_prize)	C++17	90 / 100	54 ms	5720 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> f[200005];
bool viz[200005];

vector<int> askk(int pos)
{
    if (viz[pos])
        return f[pos];
    viz[pos] = true;
    f[pos] = ask(pos - 1);
    return f[pos];
}

/*
8
3 2 3 1 3 3 2 3
*/

int find_best(int n)
{
    int sn = 500;
    sn = min(sn,n);
    int nrmax = 0,ret_sc;
    int seen = 0;
    for (int i = 1; i <= sn; i++)
    {
        vector<int> cur = askk(i);
        if (cur[0] + cur[1] == 0)
            return i - 1;
        nrmax = max(nrmax,cur[0] + cur[1]);
        if (cur[0] + cur[1] == nrmax)
            ret_sc = cur[1];
    }
    for (int i = 1; i <= sn; i++)
        if (askk(i)[0] + askk(i)[1] < nrmax)
            seen++;
    int cate = nrmax;
    set<int> pozi;
    int p = sn + 1;
    while (true)
    {
        int st = p;
        int dr;
        if (pozi.empty() or ((*pozi.rbegin()) < p))
            dr = n;
        else
            dr = *pozi.lower_bound(st);
        dr = min(dr,st + (n - st) / (cate - seen) + 5);
        vector<int> lol = askk(dr);
        if (lol[0] + lol[1] == nrmax and lol[1] == ret_sc)
        {
            p = dr + 1;
            continue;
        }
        while (st < dr)
        {
            int mij = (st + dr) / 2;
            vector<int> cur = askk(mij);
            if (cur[0] + cur[1] < nrmax)
                pozi.insert(mij),dr = mij;
            else
            {
                if (cur[1] == ret_sc)
                    st = mij + 1;
                else
                    dr = mij;
            }
        }
        while (true)
        {
            vector<int> cur = askk(st);
            if (cur[0] + cur[1] == 0)
                return st - 1;
            st++;
            p = st;
            if (cur[0] + cur[1] == nrmax)
            {
                ret_sc = cur[1];
                break;
            }
        }
    }
}

///a[i] = tipul lui i, nu prea imi pasa cat e V dar ce stiu e ca sunt sub sqrt(N) a[i] < V
///o sa incerc sa le gasesc pe fiecare in parte si dau query in ele
///pai mai intai gasesc primul de tip V, apoi voi tot incerca sa gasesc primul de tip < V de dupa si apoi brut pana la urmatorul de tip V
///asta cu binara, sigur da 90 ca e sqrtlog dar poate mai mult

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

prize.cpp: In function 'int find_best(int)':
prize.cpp:67:17: warning: 'ret_sc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |                 if (cur[1] == ret_sc)
      |                 ^~

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