Submission #294817

#	Time	Username	Problem	Language	Result	Execution time	Memory
294817		dandrozavr	The Big Prize (IOI17_prize)	C++14	92.96 / 100	84 ms	3172 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


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]);
}

set < int > ava, del;
vector < int > Del;
vector < int > mark[1001];
void correct(int pos, int last = -1){
//    if (pos == 99999) cerr << last _ byl[pos] _ ty[pos].F _ ty[pos].S << endl;
    if (last == -1){
        if (Del.size() == 0) return;
//        cout << pos _ byl[pos] _ Del.back() << endl;
        for (auto last : Del){
//            cout << last << " ";
            if (last >= byl[pos]) continue;
            int pp = lower_bound(mark[last].begin(), mark[last].end(), pos) - mark[last].begin();
            byl[pos] = last;
            ty[pos] = {ty[pos].F - pp, ty[pos].S - (mark[last].size() - pp)};
//            if (pos == 99999)
//                cerr << last _ pos _ mark[last].size() _ pp _ ty[pos].F _ ty[pos].S << endl;
        }
//        cout<<endl;
        return;
    }
    int pp = lower_bound(mark[last].begin(), mark[last].end(), pos) - mark[last].begin();
    byl[pos] = last;
    ty[pos] = {ty[pos].F - pp, ty[pos].S - (mark[last].size() - pp)};
}


void solve(int l, int r, int nsum){
    if (l + 1 >= r){
        for (; l <= r; ++l){
            if (byl[l]) continue;
            ty[l] = Ask(l);
            byl[l] = ty[l].F + ty[l].S;
        }
        return;
    }
    int mid = (l + r) >> 1;
    int m1 = mid, m2 = mid;
    for (; m1 >= l; --m1){
        ty[m1] = Ask(m1);
        byl[m1] = ty[m1].F + ty[m1].S;
        correct(m1);
        if (byl[m1] == nsum) break;
    }
    for (; m2 <= r; ++m2){
        ty[m2] = Ask(m2);
        byl[m2] = ty[m2].F + ty[m2].S;
        correct(m2);
        if (byl[m2] == nsum) break;
    }
    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);
}

mt19937_64 gen1(chrono::high_resolution_clock::now().time_since_epoch().count());

int find_best(int n) {
    int bg = 473; // 370
	int cnst1 = min(n, bg);
	int cnst2 = min(n, bg);
	int pz = gen1() % n;
    auto RES = Ask(pz);
    int mx = RES.F + RES.S;
    byl[pz] = mx;
    ty[pz] = RES;
    mx = -1;
	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;
        if (sum == mx && n > 10000) break;
    }
    for (int i = n - 1; i >= n - cnst2; --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;
        if (sum == mx && n > 10000) break;
    }
    int last = -1;
    while(true){
        if (ava.size() == 0) break;
        int x = (*ava.rbegin());
//        cout << ava.size() _ x _ byl[99999] << endl;
        del.insert(x);
        Del.pb(x);
        ava.erase(x);
        for (int i = 0; i < n; ++i)
            if (byl[i] == x){
                mark[x].pb(i);
            }
        for (int i = 0; i < n; ++i)
            if (byl[i] > x){
                correct(i, x);
            }

        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;
            }
//        cerr << x _ lef _ rig _ all << endl;
        if (lef >= rig){
            cout << "BUG" << endl;
            exit(0);
        }
        solve(lef, rig, x);
        last = x;
        for (int i = 0; i < n; ++i){
            if (byl[i] && !del.count(byl[i]) && !ava.count(byl[i])){
                ava.insert(byl[i]);
//                cout << i _ byl[i] << "\n";
            }
        }
//        cout<<endl;
    }
    int ans = -1, cnt = 0;
    for (int i = 0; i < n; ++i)
    if (byl[i] == 0 && used[i]){
//        cout << i << endl;
        ++cnt;
        ans = i;
    }

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

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:117:9: warning: variable 'last' set but not used [-Wunused-but-set-variable]
  117 |     int last = -1;
      |         ^~~~

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