Submission #390559

#	Time	Username	Problem	Language	Result	Execution time	Memory
390559		mehrdad_sohrabi	The Big Prize (IOI17_prize)	C++14	100 / 100	85 ms	11436 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
typedef long long int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=2e5+100;
/*
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<int32_t> 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<int32_t> res(2);
	res[0] = rank_count[g[i] - 1][i + 1];
	res[1] = rank_count[g[i] - 1][n] - res[0];
	return res;
}
*/
ll fen[N];
void add(ll idx,ll val){
    for (;idx<N;idx+=idx & -(idx)){
        fen[idx]+=val;
    }
}
ll get(ll idx){
    ll s=0;
    for (;idx;idx-=idx & (-idx)){
        s+=fen[idx];
    }
    return s;
}
ll val[N];
pii a[N];
ll mx=0;
pii ASK(int i){
    if (val[i]==-1){
        vector <int32_t> ans=ask(i);
        a[i]={ans[0],ans[1]};
        val[i]=a[i].F+a[i].S;
    }
    return a[i];
}
ll vis[N];
ll aaa=-1;
void solve(ll l,ll r,ll kl,ll kr){
    if (kl+kr+(get(r)-get(l))>=mx || aaa!=-1) return ;
    vector <int> cand;
    for (int i=l;i<r;i++){
        if (vis[i]){
            cout << 1/0;
        }
        cand.pb(i);
    }
    ll s=cand.size();
    s/=2;
    if (cand.size()==0) return ;
    if (cand.size()==1){

        ASK(cand[0]);
        if (val[cand[0]]<mx){
            vis[cand[0]]=1;

        }
     //   if (val[cand[0]]>mx) cout << 1/0;
        return ;
    }
    ll mid=cand[s-1]+1;
    ll p1=0,p2=0;
    for (int i=s;i<cand.size();i++){
        if (aaa!=-1) return ;
        ASK(cand[i]);
        if (val[cand[i]]<mx){
            vis[cand[i]]=1;
            if (val[cand[i]]==0) aaa=cand[i];
            if (a[cand[i]].F==0) p1=0;
            if (a[cand[i]].S==0) p2=0;
            continue;
        }
        if (val[cand[i]]>mx) cout << 1/0;
        if (i!=cand.size()-1 && p1==0){
            solve(cand[i+1],r,a[cand[i]].F,kr);
        }
        if (p2==0)
        solve(l,mid,kl,a[cand[i]].S+i-s);
        return ;
    }
    if (aaa!=-1 || p1==1) return ;
    solve(l,mid,kl,kr+cand.size()-s);
}
int32_t find_best(int32_t n) {
	memset(val,-1,sizeof val);
	vector <int> rnd;
	for (int i=0;i<n;i++){
        rnd.pb(i);
	}
	random_shuffle(rnd.begin(),rnd.end());
	/*
	if (n>1000){
        ll s=0;
        ll K=500;
        for (int i=s;i<s+K;i++){
            ASK(i);
            mx=max(mx,val[i]);
            if (val[i]==0) return i;
        }
        ll tt=0;
        for (int i=0;i<K;i++){
            if (val[i]!=mx) tt++;
        }
        solve(K,n,tt,0);

	}
	else{
    */
    ll kk=448;
	for (int i=0;i<min((ll)n,kk);i++){
        ASK(rnd[i]);
        mx=max(mx,val[rnd[i]]);
        if (val[rnd[i]]==0) return rnd[i];
        if (val[rnd[i]]>50){
            kk=i+1;
            break;
        }
	}
	for (int i=0;i<min((ll)n,kk);i++){
        if (val[rnd[i]]!=mx){
            add(rnd[i]+1,1);
        }
	}
	solve(0,n,0,0);

	for (int i=0;i<n;i++){
        if (vis[i]==1 && val[i]==0) return i;
	}
	return 0;
}
/*
int32_t main() {
	cin >> n;

	g.resize(n);
	for(int i = 0; i < n; i++) {
		//cin >> g[i];
		g[i]=2;
		if(g[i] < 1) {
			cerr << "Invalid rank " << g[i] << " at index " << i << endl;
			exit(0);
		}
	}
    ll z=rand()%n;
    g[z]=1;
    cout << z << endl;
	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;
}
*/
/*
8
3 2 3 1 3 3 2 3
*/

Compilation message (stderr)

prize.cpp: In function 'void solve(ll, ll, ll, ll)':
prize.cpp:72:22: warning: division by zero [-Wdiv-by-zero]
   72 |             cout << 1/0;
      |                     ~^~
prize.cpp:91:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for (int i=s;i<cand.size();i++){
      |                  ~^~~~~~~~~~~~
prize.cpp:101:39: warning: division by zero [-Wdiv-by-zero]
  101 |         if (val[cand[i]]>mx) cout << 1/0;
      |                                      ~^~
prize.cpp:102:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         if (i!=cand.size()-1 && p1==0){
      |             ~^~~~~~~~~~~~~~~

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