제출 #1168793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168793		Boycl07	The Big Prize (IOI17_prize)	C++20	100 / 100	18 ms	11760 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 = 448;
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 = -1;
int num = 0;
set<int> s[N];
pii get(int x)
{
    if(used[x]) return dat[x];
    vector<int> tmp = ask(x);
    used[x] = 1;
    dat[x] = {tmp[0], tmp[1]};
    s[tmp[0] + tmp[1]].insert(x);

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

    return dat[x];
}

int num_iter = 0;


void dnc_calc(int l, int r)
{
    if(ans != -1) return;
    if(l > r) return;
    if(l == r) return get(l), void();
    int mid = l + r >> 1;
    int mid_sum = get(mid).fi + get(mid).se;
    auto it = s[mid_sum].lower_bound(mid);
    if(it == s[mid_sum].begin() || dat[*prev(it)].fi != dat[mid].fi)
        dnc_calc(l, mid - 1);
    it = s[mid_sum].lower_bound(mid);
    if(next(it) == s[mid_sum].end() || dat[*next(it)].se != dat[mid].se)
        dnc_calc(mid + 1, r);
}

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

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