Submission #512991

#	Time	Username	Problem	Language	Result	Execution time	Memory
512991		kevinxiehk	The Big Prize (IOI17_prize)	C++17	20 / 100	3047 ms	12520 KiB

prize

#include "prize.h"
#include "bits/stdc++.h"
using namespace std;
int ddd = 1;
int fen[200005][20];
int corr[20];
int n;
unordered_map<int, int> aaa;
void add(int id, int x, int k) {
    id++;
    while(id <= n + 3) {
        fen[id][k] += x;
        id += (id & (-id));
    }
}
int sum(int id, int k) {
    int ans = 0;
    id++;
    while(id > 0) {
        ans += fen[id][k];
        id -= (id & (-id));
    }
    return ans;
}    
int getbefore(int id, int k) {
    int t = 0;
    for(int i = 1; i < ddd; i++) {
        if(corr[i] < k) t += sum(id, i);
    }
    return t;
}
void add_val(int a, int k) {
    if(aaa[k] == 0) {corr[ddd] = k; aaa[k] = ddd++;}
    add(a, 1, aaa[k]);
}
bool vi[200005];
bool vi2[200005];
vector<int> store[200005];
int now = 0;
int dx = 0;
int sign = 1;
int mx = 0;
int ans = -1;
vector<int> aa(int t) {
    cerr << t << '\n';
    vector<int> res;
    if(vi[t]) {
        return store[t];
        // int k = 0;
        // while((t - k < 0 ||vi[t - k]) && (t + k >= n || vi[t + k])) k++;
        // if(t - k >= 0 && !vi[t - k]) now = t = t - k;
        // else now = t = t + k;
    }
    vi[t] = true;
    res = ask(t);
    if(res[0] + res[1] == 0) ans = t;
    add_val(t, res[0] + res[1]);
    // if(res[0] + res[1] < mx && t > 0) aa(t - 1);
    now++;
    // assert(now <= 10000);
    // vi[t] = true;
    return store[t] = res;
}
int ll = 1000, rr = n - 1;
void solve(int l, int r) {
    cerr << l << ' ' << r << '\n';
    if(l > r) return;
    while(aa(l)[0] + aa(l)[1] < mx) l++;
    while(aa(r)[0] + aa(r)[1] < mx) r--;
    if(!(aa(l)[0] <= getbefore(l, mx))) return;
    if(l > r) return;
    if(l + 1 == r) {
        aa(l); aa(r);
        return;
    }
    int m = (l + r) / 2;
    vector<int> res = aa(m);
    if(l == r) return;
    // vector<int> res = aa(m);
    // if(res[0] + res[1] == 0) {ans = m; return;}
    for(int k = 0; k < r - l; k++) {
        if(m + k <= r && aa(m + k)[1] + aa(m + k)[0] == mx) {
            m += k;
            break;
        } 
        if(m - k >= l && aa(m - k)[1] + aa(m - k)[0] == mx) {
            m -= k;
            break;
        } 
    }
    // if(m == l && res[0] + res[1] < mx) {
    //     ll = max(ll, (l + r) / 2 + 1);
    //     return;
    // }
    // if(res[1] == 0) rr = m - 1;
    // if(l == r) {
    //     ll = m + 1;
    //     return;
    // }
    if(res[0] > getbefore(m, res[0] + res[1])) {
        solve(l, m);
        // vi2[m] = true;
    }
    else if(res[0] == getbefore(m, res[0] + res[1])) {
        // ll = max(ll, m + 1);
        solve(m + 1, r);
        // return;
    }
    else while(1);
}
int find_best(int N) {
    for(int i = 0; i < 1000; i++) {
		vector<int> res = aa(i);
		if(res[0] + res[1] == 0) return i;
        mx = max(mx, res[0] + res[1]);
	}
    n = N;
    rr = n - 1;
    // int t = 100;
    while(ans == -1) {
        cerr << "e\n";
        // assert(aa(ll)[0] <= getbefore(ll, mx));
        solve(ll, rr);
        // cerr << now << '\n';
        // vector<int> res = aa(now);
		// if(res[0] + res[1] == 0) return now;
        // if(!vi[now]) add_val(now, res[0] + res[1]);
        // vi[now] = true;
        // if(res[0] <= getbefore(now, res[0] + res[1])) {
        //     sign = 1;
        //     dx *= 2;
        //     if(dx == 0) dx++;
        // }
        // else {
        //     sign = -1;
        //     dx /= 2;
        //     if(dx == 0) dx++;
        // }
        
        // if(sign == 1) dx = min(dx, n - 1 - now);
        // else dx = min(dx, now);
        // now += dx * sign;
    }
    return ans;
	// for(int i = 0; i < n; i++) {
	// 	vector<int> res = ask(i);
	// 	if(res[0] + res[1] == 0)
	// 		return i;
	// }
	// return 0;
}

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