Submission #429962

#	Time	Username	Problem	Language	Result	Execution time	Memory
429962		2fat2code	The Big Prize (IOI17_prize)	C++17	20 / 100	61 ms	1200 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define fr first
#define sc second
//#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int xmax = 500;
const int blocksize = 400;

int maxi = 0, cnt = 1, l[50000], r[50000], nrblockuri, asked[200005], bune[50000];

int find_best(int n) {
	for(int i=0;i<min(n, xmax);i++){
        vector<int>arr = ask(i);
        maxi = max(maxi, arr[0] + arr[1]);
	}
	nrblockuri = (n - 1)/ blocksize;
	for(int i=0;i<=nrblockuri;i++){
        l[i] = i*blocksize;
        r[i] = min(n-1, (i + 1) * blocksize - 1);
	}
    for(int i=0;i<=nrblockuri;i++){
        while(l[i] <= r[i]){
            vector<int>rs = ask(l[i]);
            if(!(rs[0] + rs[1])){
                return l[i];
            }
            asked[l[i]] = rs[1];
            if((rs[0] + rs[1]) != maxi){
                l[i]++;
                bune[i]++;
            }
            else{
                break;
            }
        }
    }
    for(int i=0;i<=nrblockuri;i++){
        cnt += bune[i];
        if(l[i] <= r[i]){
            if(i == nrblockuri || (l[i+1] == r[i+1] + 1) || asked[l[i]] > asked[l[i+1]] - bune[i+1]){
                if(i == nrblockuri || (l[i+1] == r[i + 1] + 1)){
                    int ok = l[i];
                    while(true){
                        int le = ok + 1;
                        int ri = r[i];
                        ok = -1;
                        while(le <= ri){
                            int mid = le + (ri - le) / 2;
                            vector<int>rs = ask(mid);
                            if((rs[0] + rs[1]) == maxi){
                                if(rs[0] >= cnt){
                                    ri = mid - 1;
                                }
                                else{
                                    le = mid + 1;
                                }
                            }
                            else{
                                if(!(rs[0] + rs[1])){
                                    return mid;
                                }
                                ok = mid;
                                ri = mid - 1;
                            }
                        }
                        if(ok == -1){
                            break;
                        }
                        cnt++;
                    }
                }
                else{
                    int ok = l[i];
                    for(int j=1;j<=(asked[l[i]] - (asked[l[i+1]] - bune[i+1]));j++){
                        int le = ok + 1;
                        int ri = r[i];
                        ok = -1;
                        while(le <= ri){
                            int mid = le + (ri - le) / 2;
                            vector<int>rs = ask(mid);
                            if((rs[0] + rs[1]) == maxi){
                                if(rs[0] >= cnt){
                                    ri = mid - 1;
                                }
                                else{
                                    le = mid + 1;
                                }
                            }
                            else{
                                if(!(rs[0] + rs[1])){
                                    return mid;
                                }
                                ok = mid;
                                ri = mid - 1;
                            }
                        }
                        cnt++;
                    }
                }
            }
        }
	}
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:114:1: warning: control reaches end of non-void function [-Wreturn-type]
  114 | }
      | ^

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