제출 #429906

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
429906		2fat2code	The Big Prize (IOI17_prize)	C++17	90 / 100	98 ms	1180 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 = 1000;

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]);
        if(!(arr[0] + arr[1])){
            return i;
        }
	}
	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]){
                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++;
                }
            }
        }
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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

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