#include <bits/stdc++.h>
#define N 200050
#include "prize.h"
using namespace std;
int n, v[N], maior, ans, raiz;
vector<int> dp[N];
vector<int> aski(int x)
{
if(!dp[x].empty()) return dp[x];
return dp[x] = ask(x);
}
#define f first
#define s second
typedef pair<int, int> pii;
vector<int> bucket[500];
int solve(int p, int en)
{
while(p <= en)
{
vector<int> aux = aski(p);
if(aux[0] + aux[1] == 0) return p;
int ini = p + 1, fim = n - 1, mid;
if(aux[0] + aux[1] == maior)
{
while(fim >= ini)
{
mid = (ini + fim)/2;
vector<int> atual = aski(mid);
if(atual[0] + atual[1] == 0) return mid;
if(ini == fim) break;
if(atual[0] + atual[1] < maior) fim = mid;
else
{
if(aux[1] - atual[1] > 0) fim = mid - 1;
else ini = mid + 1;
}
}
p = ini + 1;
} else p++;
}
return -1;
}
int find_best(int n)
{
raiz = sqrt(n) + 1;
for(int i = 0; i < n; i ++ ) bucket[i/raiz].push_back(i);
for(int i = 0; i <= min(n - 1, raiz); i++)
{
vector<int> aux = aski(i);
if(aux[0] + aux[1] == 0) return i;
maior = max(maior, aux[0] + aux[1]);
}
for(int i = 0; i < 500; i++)
{
if(bucket[i].empty()) continue;
int a = bucket[i][0], b = bucket[i].back();
int ans = solve(a, b);
if(ans > -1) return ans;
}
}
Compilation message
prize.cpp: In function 'int find_best(int)':
prize.cpp:86:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
63 ms |
8700 KB |
Incorrect |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
39 ms |
8700 KB |
Incorrect |
2 |
Halted |
0 ms |
0 KB |
- |