Submission #429735

#	Time	Username	Problem	Language	Result	Execution time	Memory
429735		2fat2code	커다란 상품 (IOI17_prize)	C++17	0 / 100	19 ms	1944 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, l[5000], r[5000], nrblockuri, asked[200005], bune[5000];

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]);
            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]]){
                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++;
                }
            }
        }
	}
}

Compilation message (stderr)

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

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