제출 #974113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
974113		__Davit__	The Big Prize (IOI17_prize)	C++17	100 / 100	29 ms	2136 KiB

prize

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

#define ll long long
#define lld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define vr(v) v.begin(),v.end()
#define rv(v) v.rbegin(),v.rend()
using namespace std;

namespace RND {

    mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());

    ll RANDOM(ll l, ll r) {
        ll res = myrand() % (r - l + 1) + l;
        return res;
    }

    void shuffle(vector<int> &a) {
        for (int i = 0; i < (int) a.size(); i++) {
            int idx = RANDOM(0, (int) a.size() - 1);
            swap(a[i], a[idx]);
        }
    }
};
namespace {
    const int N = 2e5 + 5;
    int answer = -1;
    int A[N][2];
};

void harc(int x) {
    if (A[x][0] == -1) {
        vector<int> tmp = ask(x);
        A[x][0] = tmp[0];
        A[x][1] = tmp[1];
    }
    if (A[x][0] + A[x][1] == 0) {
        answer = x;
        return;
    }
}


int Rank(int x) {
    harc(x);
    return A[x][0] + A[x][1];
}

int pref(int x) {
    harc(x);
    return A[x][0];
}

void solve(int start, int end) {
    if (answer != -1)return;
    if (start == end) {
        harc(start);
        return;
    }
    while (Rank(start) != Rank(end)) {
        if (Rank(start) < Rank(end))start++;
        else end--;
    }
    if (A[start][0] == A[end][0])return;

    int mid = (start + end) >> 1;
    solve(start, mid);
    solve(mid, end);
}

int find_best(int n) {
    for (int i = 0; i < N; i++)A[i][0] = -1;
    solve(0, n - 1);
    return answer;
}

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