Submission #1253862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253862		Cookie	The Big Prize (IOI17_prize)	C++20	20 / 100	28 ms	6160 KiB

prize

//#include "prize.h"
#include<bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#define sz(v) (int)v.size()
#define fi first
#define se second
using namespace std;

static const int max_q = 10000;
static int n;
static int query_count = 0;
static vector<int> g;
static vector<vector<int> > rank_count;
//#include "prize.h"
vector<int>ask(int);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rr(int l, int r){
    return(uniform_int_distribution<int>(l, r)(rng));
}
int N = 2e5 + 5;
int MX = 0;
vector<pair<int, int>>special;
vector<int>memo[200005];
set<int>unvisited;
int Q = 10000;
int bit[200005 + 1];
void upd(int p, int v){
    while(p <= N){
        bit[p] += v; p += p & (-p);
    }
}
int gett(int p){
    int ans = 0;
    while(p){
        ans  += bit[p]; p -= p & (-p);
    }
    return(ans);
}
int kth(int x){
    int pos = 0, sm = 0;
    for(int i = 17; i >= 0; i--){
        if(pos + (1 << i) <= N && bit[pos + (1 << i)] + sm < x){
            pos += (1 << i); sm += bit[pos];
        }
    }
    return(pos + 1);
}
pair<vector<int>, bool>get(int x){

    if(sz(memo[x]) == 2)return(make_pair(memo[x], 0));
    Q--;
    memo[x] = ask(x);
    if(memo[x][0] + memo[x][1] < MX){
        special.push_back(make_pair(x, memo[x][0] + memo[x][1]));
        return(make_pair(memo[x], 1));
    }
    return(make_pair(memo[x], 0));
}
int find_best(int n) {
    N = n;
	int pos, L = 1, R = n, cntzero = 0, cntone = 0;
	for(int i = 0; i < n; i++){
        upd(i + 1, 1);
	}
	for(int i = 0; i < 450; i++){
        int cand = i; get(cand);
        MX = max(MX, memo[cand][0] + memo[cand][1]);
        memo[cand].clear();
	}
	special.clear();
    while(Q){
        //assert(L <= R);
        int mid = (L + R) >> 1;
        //cerr << mid << "\n";
        pos = kth(mid) - 1;
        assert(sz(memo[pos]) == 0);
        upd(pos + 1, -1);
        //assert(pos >= L && pos <= R);
        auto [cnt, isspecial] = get(pos);
        if(cnt[0] + cnt[1] == 0)return(pos);
        int rnk = cnt[0] + cnt[1];
        for(auto i: special){
            if(i.se < rnk){
                if(i.fi < pos){
                    cnt[0]--;
                }else if(i.fi > pos){
                    cnt[1]--;
                }
            }
        }
        assert(cnt[0] >= 0 && cnt[1] >= 0);
        //assert(isspecial || (cnt[0] >= cntzero && cnt[1] >= cntone));
        cnt[0] -= cntzero; cnt[1] -= cntone;
        if(cnt[0] > cnt[1]){
            R = mid - 1;
            cntone += cnt[1];
        }else{

            L = mid; R--;
            cntzero += cnt[0];
        }
        if(isspecial){
            L = 1; R = gett(n); cntzero = cntone = 0;
        }
        //assert(cnt[0] || cnt[1]);
    }
    //assert(0);
    return(1);
}
/*
vector<int> ask(int i) {
	query_count++;
	if(query_count > max_q) {
		cerr << "Query limit exceeded" << endl;
		exit(0);
	}

	if(i < 0 || i >= n) {
		cerr << "Bad index: " << i << endl;
		exit(0);
	}

	vector<int> res(2);
	res[0] = rank_count[g[i] - 1][i + 1];
	res[1] = rank_count[g[i] - 1][n] - res[0];
	return res;
}

int main() {
	cin >> n;

	g.resize(n);
	for(int i = 0; i < n; i++) {
		cin >> g[i];
		if(g[i] < 1) {
			cerr << "Invalid rank " << g[i] << " at index " << i << endl;
			exit(0);
		}
	}

	int max_rank = *max_element(g.begin(), g.end());

	rank_count.resize(max_rank + 1, vector<int>(n + 1, 0));
	for(int r = 0; r <= max_rank; r++) {
		for(int i = 1; i <= n; i++) {
			rank_count[r][i] = rank_count[r][i - 1];
			if(g[i - 1] == r)
			  rank_count[r][i]++;
		}
	}

	for(int i = 0; i <= n; i++)
		for(int r = 1; r <= max_rank; r++)
			rank_count[r][i] += rank_count[r - 1][i];

	int res = find_best(n);
	cout << res << endl << "Query count: " << query_count << endl;
	return 0;
}
*/

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