Submission #642844

#	Time	Username	Problem	Language	Result	Execution time	Memory
642844		Alexandruabcde	The Big Prize (IOI17_prize)	C++14	0 / 100	5 ms	9692 KiB

prize

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

using namespace std;

typedef pair <int, int> PII;

constexpr int NMAX = 2e5 + 5;

set <int> S[NMAX];
int ans;
int CntStanga[NMAX];

void DivideConquer (int Left, int Right) {
    if (Left > Right) return;

    int mid = (Left + Right) / 2;
    vector <int> a = ask(mid);
    int tip = a[0] + a[1];
    CntStanga[mid] = a[0];

    if (tip == 0) {
        ans = mid;
        return;
    }

    auto it = S[tip].insert(mid).first;

    if (it == S[tip].begin())
        DivideConquer(Left, mid-1);
    else if (CntStanga[*prev(it)] != CntStanga[mid]) DivideConquer(Left, mid-1);

    if (ans == -1) return;

    if (it == prev(S[tip].end()))
        DivideConquer(mid + 1, Right);
    else if (CntStanga[*next(it)] != CntStanga[mid]) DivideConquer(mid+1, Right);
}

int find_best(int n) {
    ans = -1;

    DivideConquer(0, n-1);

	return ans;
}

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