제출 #1271930

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271930		Aviansh	The Big Prize (IOI17_prize)	C++20	0 / 100	3 ms	436 KiB

prize

#include "prize.h"

#include <bits/stdc++.h>

using namespace std;

map<int,vector<int>>mp;
int N;
int cutoff;
vector<int>kask(int n){
    if(n<0||n>=N){
        return {0,0};
    }
    if(mp.find(n)!=mp.end()){
        return mp[n];
    }
    return mp[n]=ask(n);
}

int locate(int x){
    if(x<0||x>=N){
        return x;
    }
    for(int i = 0;i<N;i++){
        if(x+i<N&&kask(x+i)[0]+kask(x+i)[1]==cutoff){
            return x+i;
        }
        if(x-i>=0&&kask(x-i)[0]+kask(x-i)[1]==cutoff){
            return x-i;
        }
    }
}

int find_best(int n) {
    mp.clear();
    N=n;
    cutoff=0;
    for(int i = 0;i<min(n,474);i++){
        if(kask(i)[0]+kask(i)[1]>cutoff){
            cutoff=kask(i)[0]+kask(i)[1];
        }
    }
    queue<array<int,3>>q;
    int mid = locate(n/2);
    q.push({0,mid-1,kask(mid)[0]});
    q.push({mid+1,n-1,kask(mid)[1]});
    if(kask(mid)[0]==0&&kask(mid)[1]==0){
        return mid;
    }
    while(!q.empty()){
        array<int,3>a = q.front();
        q.pop();
        if(a[2]==0)
            continue;
        if(abs(a[2]-(a[1]-a[0]))<=4){
            for(int i = a[0];i<=a[1];i++){
                if(kask(i)[0]+kask(i)[1]==0){
                    return i;
                }
            }
            continue;
        }
        int l = locate(a[0]-1);
        int r = locate(a[1]+1);
        int mid=locate((l+r)/2);
        q.push({l,mid,kask(mid)[0]-kask(l)[0]});
        q.push({mid,r,kask(mid)[1]-kask(r)[1]});
    }
	return -1;
}

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

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

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