// In The Name Of The Queen
#include<bits/stdc++.h>
#include "xylophone.h"
using namespace std;
int n;
vector < int > A, M;
inline int GetNext(int i)
{
int df = query(i, i + 1);
int v1 = A[i] - df;
int v2 = A[i] + df;
if (v1 < 1 || M[v1])
return (v2);
if (v2 > n || M[v2])
return (v1);
int Mn = A[i], Mx = A[i], j = i;
for (j = i; v1 <= Mn && Mx <= v2; j --)
Mn = min(Mn, A[j]),
Mx = max(Mx, A[j]);
df = query(j, i + 1);
if (df == Mx - Mn)
return (Mx <= v2 ? v1 : v2);
return (Mx <= v2 ? v2 : v1);
}
inline int GetPrev(int i)
{
int df = query(i - 1, i);
int v1 = A[i] - df;
int v2 = A[i] + df;
if (v1 < 1 || M[v1])
return (v2);
if (v2 > n || M[v2])
return (v1);
int Mn = A[i], Mx = A[i], j = i;
for (j = i; v1 <= Mn && Mx <= v2; j ++)
Mn = min(Mn, A[j]),
Mx = max(Mx, A[j]);
df = query(i - 1, j);
if (df == Mx - Mn)
return (Mx <= v2 ? v1 : v2);
return (Mx <= v2 ? v2 : v1);
}
void solve(int _n)
{
n = _n;
int le = 1, ri = n, md;
while (ri - le > 1)
{
md = (le + ri) >> 1;
if (query(md, n) == n - 1)
le = md;
else
ri = md;
}
A = vector < int > (n + 1, 0);
M = vector < int > (n + 1, 0);
A[le] = 1; M[1] = 1;
for (int i = le + 1; i <= n; i ++)
A[i] = GetNext(i - 1), M[A[i]] = 1;
for (int i = le - 1; i; i --)
A[i] = GetPrev(i + 1), M[A[i]] = 1;
for (int i = 1; i <= n; i ++)
answer(i, A[i]);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
248 KB |
Output is correct |
2 |
Correct |
5 ms |
248 KB |
Output is correct |
3 |
Runtime error |
7 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
248 KB |
Output is correct |
2 |
Correct |
5 ms |
248 KB |
Output is correct |
3 |
Runtime error |
7 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
248 KB |
Output is correct |
2 |
Correct |
5 ms |
248 KB |
Output is correct |
3 |
Runtime error |
7 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |