Submission #430340

#	Time	Username	Problem	Language	Result	Execution time	Memory
430340		2fat2code	The Big Prize (IOI17_prize)	C++17	100 / 100	82 ms	6712 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 = 447;

int maxi = 0, cnt = 1, l[50000], r[50000], nrblockuri, asked[200005], bune[50000], viz[200005];
vector<int>remember[200005];

int find_best(int n) {
	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++){
        vector<int>arr = ask(l[i]);
        if(!(arr[0] + arr[1])){
            return l[i];
        }
        viz[l[i]] = 1;
        remember[l[i]] = arr;
        maxi = max(maxi, arr[0] + arr[1]);
	}
	for(int i=1;i<=min(50,n - 1);i++){
        vector<int>arr = ask(i);
        if(!(arr[0] + arr[1])){
            return i;
        }
        viz[i] = 1;
        remember[i] = arr;
        maxi = max(maxi, arr[0] + arr[1]);
	}
    for(int i=0;i<=nrblockuri;i++){
        while(l[i] <= r[i]){
            vector<int>rs;
            if(!viz[l[i]]){
                viz[l[i]] = 1;
                rs = ask(l[i]);
            }
            else{
                rs = remember[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]){
            int nrfolosiri = 0;
            for(int j=i+1;j<=nrblockuri;j++){
                nrfolosiri += bune[j];
                if(l[j] != r[j] + 1){
                    nrfolosiri += asked[l[j]];
                    break;
                }
            }
            int ok = l[i];
            nrfolosiri = asked[l[i]] - nrfolosiri;
            for(int j=1;j<=nrfolosiri;j++){
                int le = ok + 1;
                int ri = r[i];
                ok = -1;
                int hahah = 0;
                while(le <= ri){
                    hahah ++;
                    int mid = le + (ri - le) / 2;
                    vector<int>rs;
                    if(viz[mid]){
                        rs = remember[mid];
                    }
                    else{
                        viz[mid] = 1;
                        rs = ask(mid);
                        remember[mid] = rs;
                    }
                    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:120:1: warning: control reaches end of non-void function [-Wreturn-type]
  120 | }
      | ^

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