Submission #1168786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168786		Boycl07	The Big Prize (IOI17_prize)	C++20	98.01 / 100	13 ms	2172 KiB

prize

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

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 1; i <= (n); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define forn(i, l, r) for(int i = (l); (i) <= (r); ++i)
#define ford(i, r, l) for(int i = (r); (i) >= (l); --i)
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define task "note"

template<typename T> bool maximize(T &res, const T &val) {if(res < val) {res = val; return 1;} return 0;}
template<typename T> bool minimize(T &res, const T &val) {if(res < val) return 0; res = val; return 1;}
inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}
const int N = 2e5 + 3;
const int LOG = 12;
const int INF = 2e9;
const int S = 450;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
double get_cur_time() {return chrono::steady_clock::now().time_since_epoch().count();}

int n;
bool used[N];
pii dat[N];
int ans;
int num = 0;

pii get(int x)
{
    if(used[x]) return dat[x];
    vector<int> tmp = ask(x);
    used[x] = 1;
    dat[x] = {tmp[0], tmp[1]};

    if(tmp[0] + tmp[1] == 0) ans = x;

    return dat[x];
}

int num_iter = 0;


void dnc_pre(int l, int r)
{
    if(l > r) return;
    if(num_iter == S) return;
    int mid = l + r >> 1;
    pii x = get(mid);
    ++num_iter;
    maximize(num, x.fi + x.se);
    dnc_pre(l, mid - 1);
    dnc_pre(mid + 1, r);
}
void dnc_calc(int l, int r, int num_l, int num_in)
{
    if(num_in == 0) return;
    if(l > r) return;

    int mid = l + r >> 1;
    int new_num = 0;
    for(int i = mid; i >= l; --i)
    {
        pii x = get(i);
        if(x.fi + x.se == num)
        {
            new_num += x.fi - num_l;
            break;
        }
        ++new_num;
    }
    dnc_calc(l, mid - 1, num_l, new_num);
    dnc_calc(mid + 1, r, num_l + new_num, num_in - new_num);
}

int find_best(int N)
{
    n = N;
    dnc_pre(0, n - 1);
    dnc_calc(0, n - 1, 0, num);
    return ans;
}

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