Submission #129592

#	Time	Username	Problem	Language	Result	Execution time	Memory
129592		Masterdan	The Big Prize (IOI17_prize)	C++14	20 / 100	3068 ms	568 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define MIN -1
#define MAX 1000000000
#define all(a)  a.begin (), a.end ()
#define mp  make_pair
#define pb  push_back
using namespace std;
typedef vector <int> vi;
typedef long long int ll;
typedef pair <int, int> ii;
pair<int, int> v[201000];
bool aux[200100];
pair<int, int> visitado(int pos){
    if (aux[pos]){
        return v[pos];
    }
    aux[pos] = 1;
    vector <int> v1 = ask(pos);
    return v[pos] = {v1[0], v1[1]};
}

int find_best(int n) {
    int mx = MIN;
    int mxpos = 0;
    for (int i = 0; i < min(474, n); i++){
        pair<int, int> v = visitado(i);
        if (v.first+v.second == 0)
            return i;
        if (v.first + v.second > mx){
            mx = v.first + v.second;
            mxpos = i;
        }
    }
    int aux1 = mxpos;
    while(1){
        int l = aux1+1, r = n;
        while(l < r){
            int mid = (l+r)/2;
            pair<int, int> v = visitado(mid);
            if (v.first+v.second == 0)return mid;
            if (v != visitado(aux1))
                r = mid; else
                l = mid;
        }
        aux1 = l;
        while(aux1 < n){
            if (visitado(aux1).first + visitado(aux1).second == visitado(mxpos).first+visitado(mxpos).second)
                break;
            if (visitado(aux1).first + visitado(aux1).second == 0)
                return aux1;
            aux1++;
        }
    }
}
/*
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;

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