#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
map < int, vector < int > > mp;
map < int, int > used;
int cnt = 0;
vector < int > local_ask(int idx)
{
if (used[idx])
return mp[idx];
cnt ++;
//if (cnt == 1e4)
// while(true);
used[idx] = 1;
mp[idx] = ask(idx);
return mp[idx];
}
const int maxn = 2e5 + 10;
vector < int > st;
int best;
void solve_range(int l, int r)
{
cout << l << " " << r << " " << cnt << endl;
int m = (l + r) / 2;
vector < int > lf = local_ask(l);
vector < int > rf = local_ask(r);
if (lf[1] == rf[1])
return;
while(m > l)
{
vector < int > mf = local_ask(m);
if (mf[0] + mf[1] != best)
{
st.push_back(m);
m --;
}
else
{
break;
}
}
if (m == l)
{
m = (l + r) / 2 + 1;
while(m < r)
{
vector < int > mf = local_ask(m);
if (mf[0] + mf[1] != best)
st.push_back(m), m ++;
else
break;
}
}
if (m == r)
return;
vector < int > mf = local_ask(m);
if (lf[0] != mf[0])
solve_range(l, m);
if (rf[0] != mf[0])
solve_range(m, r);
}
int find_best(int n)
{
vector < int > idc;
for (int i = 0; i < n; i ++)
idc.push_back(i);
int nec = min(n, (int)sqrt(n) + 100);
int mx = -1;
for (int i = 0; i < nec; i ++)
{
vector < int > cur = local_ask(i);
if (cur[0] + cur[1] > best)
{
best = cur[0] + cur[1];
mx = i;
}
}
int pt = n - 1;
while(true)
{
vector < int > cur = local_ask(pt);
if (cur[0] + cur[1] == best)
break;
pt --;
}
for (int i = 0; i < mx; i ++)
st.push_back(i);
for (int i = pt + 1; i < n; i ++)
st.push_back(i);
solve_range(mx, pt);
//cout << st.size() << " " << cnt << endl;
for (int i = 0; i < st.size(); i ++)
{
vector < int > cur = local_ask(st[i]);
if (cur[0] + cur[1] == 0)
return st[i];
}
return -1;
}
Compilation message
prize.cpp: In function 'int find_best(int)':
prize.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for (int i = 0; i < st.size(); i ++)
| ~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
1352 KB |
Token "0" doesn't correspond to pattern "[A-B]{1}" |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
1352 KB |
Token "0" doesn't correspond to pattern "[A-B]{1}" |
2 |
Halted |
0 ms |
0 KB |
- |