Submission #294647

#	Time	Username	Problem	Language	Result	Execution time	Memory
294647		dandrozavr	The Big Prize (IOI17_prize)	C++14	20 / 100	3077 ms	1656 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define F first
#define S second
#define pii pair < int , int >
#define _ <<" "<<
#define TIME 1.0 * clock() / CLOCKS_PER_SEC

map < int , vector < int > > mp;

const int N = 2e5 + 2;
int byl[N];
pii ty[N];
bool used[N];
int all = 0;
pii Ask(int i){
    if (used[i]) return ty[i];
    ++all;
    if (all == 10000){
        while(true) continue;
    }
    auto res = ask(i);
    used[i] = 1;
    return make_pair(res[0], res[1]);
}

void solve(int l, int r, int nsum){
    if (l == r){
        if (byl[l]) return;
        ty[l] = Ask(l);
        byl[l] = ty[l].F + ty[l].S;
        return;
    }
    int mid = (l + r) >> 1;
    int m1 = mid, m2 = mid + 1;
    for (; m1 >= l; --m1){
        if (byl[m1]) continue;
        ty[m1] = Ask(m1);
        byl[m1] = ty[m1].F + ty[m1].S;
        if (byl[m1] == nsum) break;
    }
    for (; m2 <= r; ++m2){
        if (byl[m2]) continue;
        ty[m2] = Ask(m2);
        byl[m2] = ty[m2].F + ty[m2].S;
        if (byl[m2] == nsum) break;
    }
//    cout << l _ r _ mid _ m1 _ m2 << endl;
    if (l <= m1 && ty[l].F != ty[m1].F)
        solve(l, m1, nsum);
    if (r >= m2 && ty[r].F != ty[m2].F)
        solve(m2, r, nsum);
}

int find_best(int n) {
    int bg = 70; // 370
	int cnst1 = min(n, bg);
	int cnst2 = min(n, bg);
    set < int > ava, del;

	for (int i = 0; i < cnst1; ++i){
        auto res = Ask(i);
        int sum = res.F + res.S;
        if (sum == 0) return i;
        ava.insert(sum);
        byl[i] = sum;
        ty[i] = res;
    }
    for (int i = n - cnst2; i < n; ++i){
        auto res = Ask(i);
        int sum = res.F + res.S;
        if (sum == 0) return i;
        ava.insert(sum);
        byl[i] = sum;
        ty[i] = res;
    }

    while(true){
        if (ava.size() == 0) break;
        int x = (*ava.rbegin());
        int lef = n + 1, rig = - 1;
        for (int i = 0; i < n; ++i)
        if (byl[i] == x){
            if (lef == n + 1) lef = i;
            rig = i;
        }
//        cout << lef _ rig << endl;
        if (lef == rig){
            cout << "BUG" << endl;
            exit(0);
        }
        solve(lef, rig, x);
        ava.erase(x);
        del.insert(x);
        for (int i = 0; i < n; ++i)
            if (byl[i] && !del.count(byl[i]))
                ava.insert(byl[i]);
    }

    int ans = -1, cnt = 0;
    for (int i = 0; i < n; ++i)
    if (byl[i] == 0 && used[i]){
        ++cnt;
        ans = i;
    }

    if (cnt != 1){
        cout << "CNT bug" << endl;
    }
    return ans;
}

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