Submission #429662

#	Time	Username	Problem	Language	Result	Execution time	Memory
429662		2fat2code	커다란 상품 (IOI17_prize)	C++17	90 / 100	125 ms	328 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 = 450;

int maxi = 0, cnt = 1;

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]);
	}
	int blockcurr = 0, ok = -1;
	while(blockcurr <= (n - 1)/blocksize){
        int l, r;
        if(ok == -1){
            l = blockcurr * blocksize;
        }
        else{
            l = ok + 1;
            ok = -1;
        }
        r = min(n - 1, (blockcurr + 1) * blocksize - 1);
        while(l <= r){
            int mid = l + (r - l) / 2;
            vector<int>rs = ask(mid);
            if((rs[0] + rs[1]) == maxi){
                if(rs[0] >= cnt){
                    r = mid - 1;
                }
                else{
                    l = mid + 1;
                }
            }
            else{
                if(!(rs[0] + rs[1])){
                    return mid;
                }
                ok = mid;
                r = mid - 1;
            }
        }
        if(ok == -1){
            blockcurr++;
        }
        else{
            cnt++;
        }
	}
}

Compilation message (stderr)

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

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