#include "prize.h"
#include <algorithm>
#include <set>
#include <map>
std::map<int, int> mapa;
//first - sum
//second - left
int find_best(int n) {
int q = 0;
if (n <= 500)
{
std::vector<int> get;
for (int i = 0; i < n; ++i)
{
get = ask(i);
++q;
if (get[0] == 0 && get[1] == 0)
{
return i;
}
}
}
int max = 0;
std::vector<int> get;
for (int i = 0; i < 500; ++i)
{
get = ask(i);
++q;
if (get[0] + get[1] > max)
{
max = get[0] + get[1];
}
if (get[0] == 0 && get[1] == 0)
{
return i;
}
int sum = get[0] + get[1];
if (mapa.find(sum) != mapa.end())
{
mapa.insert(std::make_pair(sum, 0));
}
else
{
mapa[sum] = get[0];
}
}
int cur = 499;
std::map<int, std::pair<int, int> > askedBig;
while (1)
{
int toLeft = mapa[max];
std::set<int> asked;
bool flag = false;
for (int i = 18; i >= 0; --i)
{
int nr = 1 << i;
int toAsk = std::min(cur + nr, n - 1);
if (asked.find(toAsk) == asked.end())
{
if (askedBig.find(toAsk) != askedBig.end())
{
get[0] = askedBig[toAsk].first;
get[1] = askedBig[toAsk].second;
}
else
{
get = ask(toAsk);
++q;
if (q >= 10000)
{
while (1)
{
int x;
}
}
askedBig.insert(std::make_pair(toAsk, std::make_pair(get[0], get[1])));
}
int sum = get[0] + get[1];
if (get[0] == 0 && get[1] == 0)
{
return toAsk;
}
if (get[0] == 0)
{
mapa.insert(std::make_pair(sum, 0));
cur = toAsk;
while (1)
{
if (askedBig.find(cur + 1) != askedBig.end())
{
get[0] = askedBig[cur + 1].first;
get[1] = askedBig[cur + 1].second;
}
else
{
get = ask(cur + 1);
++q;
if (q >= 10000)
{
while (1)
{
int x;
}
}
askedBig.insert(std::make_pair(cur + 1, std::make_pair(get[0], get[1])));
}
int inner = get[0] + get[1];
if (inner == 0)
{
return cur + 1;
}
else if (inner != max)
{
mapa[inner] = get[0];
++cur;
}
else
{
mapa[inner] = get[0];
break;
}
}
flag = true;
break;
}
else if (get[0] == mapa[sum] && sum != max)
{
cur = toAsk;
while (1)
{
if (askedBig.find(cur + 1) != askedBig.end())
{
get[0] = askedBig[cur + 1].first;
get[1] = askedBig[cur + 1].second;
}
else
{
get = ask(cur + 1);
++q;
if (q >= 10000)
{
while (1)
{
int x;
}
}
askedBig.insert(std::make_pair(cur + 1, std::make_pair(get[0], get[1])));
}
int inner = get[0] + get[1];
if (inner == 0)
{
return cur + 1;
}
else if (inner != max)
{
mapa[inner] = get[0];
++cur;
}
else
{
mapa[inner] = get[0];
break;
}
}
flag = true;
break;
}
else if (get[0] == mapa[sum])
{
cur = toAsk;
}
}
}
if (!flag)
++cur;
}
}
Compilation message
prize.cpp: In function 'int find_best(int)':
prize.cpp:86:33: warning: unused variable 'x' [-Wunused-variable]
int x;
^
prize.cpp:121:33: warning: unused variable 'x' [-Wunused-variable]
int x;
^
prize.cpp:169:33: warning: unused variable 'x' [-Wunused-variable]
int x;
^
prize.cpp:62:13: warning: unused variable 'toLeft' [-Wunused-variable]
int toLeft = mapa[max];
^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
248 KB |
Output is correct |
| 2 |
Correct |
7 ms |
308 KB |
Output is correct |
| 3 |
Correct |
7 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
440 KB |
Output is correct |
| 5 |
Correct |
5 ms |
440 KB |
Output is correct |
| 6 |
Correct |
2 ms |
440 KB |
Output is correct |
| 7 |
Correct |
9 ms |
472 KB |
Output is correct |
| 8 |
Correct |
6 ms |
500 KB |
Output is correct |
| 9 |
Correct |
6 ms |
500 KB |
Output is correct |
| 10 |
Correct |
6 ms |
500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
500 KB |
Output is correct |
| 2 |
Correct |
8 ms |
684 KB |
Output is correct |
| 3 |
Correct |
7 ms |
684 KB |
Output is correct |
| 4 |
Correct |
4 ms |
684 KB |
Output is correct |
| 5 |
Correct |
7 ms |
684 KB |
Output is correct |
| 6 |
Correct |
2 ms |
684 KB |
Output is correct |
| 7 |
Correct |
7 ms |
684 KB |
Output is correct |
| 8 |
Correct |
4 ms |
684 KB |
Output is correct |
| 9 |
Correct |
7 ms |
684 KB |
Output is correct |
| 10 |
Correct |
6 ms |
684 KB |
Output is correct |
| 11 |
Execution timed out |
1063 ms |
1096 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
