#include "xylophone.h"
using namespace std;
#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <unordered_map>
//#define all(x) x.begin(), x.end()
#define pii pair<int, int>
struct pairhash
{
public:
template <typename T, typename U>
std::size_t operator()(const std::pair<T, U>& x) const
{
return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
}
};
unordered_map<pii, int, pairhash> queries;
int ownQuery(int a, int b)
{
if (queries.find({ a, b }) != queries.end())
{
return queries[{a, b}];
}
return queries[{a, b}] = query(a, b);
}
void solve(int N)
{
int a = 1, b = N;
while (a < b)
{
int k = (a + b) / 2;
int value = ownQuery(1, k);
if (value == N - 1) b = k;
else a = k + 1;
}
int maxIndex = a == b ? a : -1;
a = 1, b = maxIndex - 1;
while (a < b)
{
int k = (a + b) / 2;
int value = ownQuery(k, maxIndex);
if (value == N - 1) a = k;
else b = k - 1;
}
int oneIndex = a == b ? a : -1;
bitset<5001> found;
vector<int> values(N + 1, -1);
found[0] = true;
for (int i = N + 1; i < 5001; i++)
{
found[i] = true;
}
found[1] = true;
found[N] = true;
values[oneIndex] = 1;
values[maxIndex] = N;
bool cantProgress = true;
while (!found.all())
{
cantProgress = true;
for (int i = 1; i <= N; i++)
{
if (values[i] != -1)
{
int j = i - 1;
if (j > 0 && values[j] == -1)
{
int v = ownQuery(j, i);
int opt1 = values[i] + v;
int opt2 = values[i] - v;
if (opt1 <= 1)
{
values[j] = opt2; cantProgress = false; found[opt2] = true;
}
else if (opt2 <= 1)
{
values[j] = opt1; cantProgress = false; found[opt1] = true;
}
else if (opt1 >= N)
{
values[j] = opt2; cantProgress = false; found[opt2] = true;
}
else if (opt2 >= N)
{
values[j] = opt1; cantProgress = false; found[opt1] = true;
}
else if (found[opt1])
{
values[j] = opt2; cantProgress = false; found[opt2] = true;
}
else if (found[opt2])
{
values[j] = opt1; cantProgress = false; found[opt1] = true;
}
}
j = i + 1;
if (j < N && values[j] == -1)
{
int v = ownQuery(i, j);
int opt1 = values[i] + v;
int opt2 = values[i] - v;
if (opt1 <= 1)
{
values[j] = opt2; cantProgress = false; found[opt2] = true;
}
else if (opt2 <= 1)
{
values[j] = opt1; cantProgress = false; found[opt1] = true;
}
else if (opt1 >= N)
{
values[j] = opt2; cantProgress = false; found[opt2] = true;
}
else if (opt2 >= N)
{
values[j] = opt1; cantProgress = false; found[opt1] = true;
}
else if (found[opt1])
{
values[j] = opt2; cantProgress = false; found[opt2] = true;
}
else if (found[opt2])
{
values[j] = opt1; cantProgress = false; found[opt1] = true;
}
}
}
}
if (cantProgress) break;
}
while (!found.all())
{
cantProgress = true;
for (int i = 1; i <= N; i++)
{
if (values[i] != -1)
{
int j = i - 1;
if (j > 0 && values[j] == -1)
{
int v = ownQuery(j, i);
int opt1 = values[i] + v;
int opt2 = values[i] - v;
if (opt1 <= 1)
{
values[j] = opt2; cantProgress = false; found[opt2] = true;
}
else if (opt2 <= 1)
{
values[j] = opt1; cantProgress = false; found[opt1] = true;
}
else if (opt1 >= N)
{
values[j] = opt2; cantProgress = false; found[opt2] = true;
}
else if (opt2 >= N)
{
values[j] = opt1; cantProgress = false; found[opt1] = true;
}
else if (found[opt1])
{
values[j] = opt2; cantProgress = false; found[opt2] = true;
}
else if (found[opt2])
{
values[j] = opt1; cantProgress = false; found[opt1] = true;
}
else
{
int v2 = query(j, j + 2);
int ma = max(values[j + 2], values[i]);
int mi = min(values[j + 2], values[i]);
int v2Opt1 = max(opt1, ma) - min(opt1, mi);
int v2Opt2 = max(opt2, ma) - min(opt2, mi);
if (v2 == v2Opt1 && v2 != v2Opt2)
{
cantProgress = false;
found[opt1] = true;
values[j] = opt1;
}
else if (v2 == v2Opt2 && v2 != v2Opt1)
{
cantProgress = false;
found[opt2] = true;
values[j] = opt2;
}
else
{
cerr << "I didn't consider this to be possible. Please take a look!";
throw;
}
}
}
j = i + 1;
if (j <= N && values[j] == -1)
{
int v = ownQuery(i, j);
int opt1 = values[i] + v;
int opt2 = values[i] - v;
if (opt1 <= 1)
{
values[j] = opt2; cantProgress = false; found[opt2] = true;
}
else if (opt2 <= 1)
{
values[j] = opt1; cantProgress = false; found[opt1] = true;
}
else if (opt1 >= N)
{
values[j] = opt2; cantProgress = false; found[opt2] = true;
}
else if (opt2 >= N)
{
values[j] = opt1; cantProgress = false; found[opt1] = true;
}
else if (found[opt1])
{
values[j] = opt2; cantProgress = false; found[opt2] = true;
}
else if (found[opt2])
{
values[j] = opt1; cantProgress = false; found[opt1] = true;
}
else
{
int v2 = ownQuery(j - 2, j);
int ma = max(values[j - 2], values[i]);
int mi = min(values[j - 2], values[i]);
int v2Opt1 = max(opt1, ma) - min(opt1, mi);
int v2Opt2 = max(opt2, ma) - min(opt2, mi);
if (v2 == v2Opt1 && v2 != v2Opt2)
{
cantProgress = false;
found[opt1] = true;
values[j] = opt1;
}
else if (v2 == v2Opt2 && v2 != v2Opt1)
{
cantProgress = false;
found[opt2] = true;
values[j] = opt2;
}
else
{
cerr << "I didn't consider this to be possible. Please take a look!";
throw;
}
}
}
}
}
if (cantProgress)
{
cerr << "I didn't consider this to be possible. Please take a look!";
throw;
}
}
for (int i = 1; i <= N; i++)
{
if (values[i] == -1) throw;
answer(i, values[i]);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
208 KB |
Output is correct |
| 3 |
Execution timed out |
3086 ms |
208 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
208 KB |
Output is correct |
| 3 |
Execution timed out |
3086 ms |
208 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
208 KB |
Output is correct |
| 3 |
Execution timed out |
3086 ms |
208 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
