Submission #294707

#	Time	Username	Problem	Language	Result	Execution time	Memory
294707		dandrozavr	The Big Prize (IOI17_prize)	C++14	90 / 100	129 ms	3096 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]);
}

set < int > ava, del;
vector < int > Del;
vector < int > mark[1001];
void correct(int pos, int last = -1){
    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)};
        }
//        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 == 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 (nsum == 19)
//            cout << byl[m1] _ nsum  << endl;
        correct(m1);
//        if (nsum == 19)
//            cout << byl[m1] _ nsum  << endl<<endl;
        if (byl[m1] == nsum) break;
    }
//    cout << l _ r _ m1 _ m2 _ all _ last << endl;
    for (; m2 <= r; ++m2){
        if (byl[m2]) continue;
        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);
}

int find_best(int n) {
    int bg = 370; // 370
	int cnst1 = min(n, bg);
	int cnst2 = min(n, bg);

	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;
    }
    int last = -1;
    while(true){
        if (ava.size() == 0) break;
        int x = (*ava.rbegin());
        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;
        }
        if (lef == rig){
            cout << "BUG" << endl;
            exit(0);
        }
        solve(lef, rig, x);
//        cout << x _ lef _ rig _ all << endl;
        last = 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;
}

Compilation message (stderr)

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

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