#include "xylophone.h"
#include<iostream>
using namespace std;
int A[5001];
bool used[5001];
int NN;
bool is_valid(int x)
{
return (1 <= x && x<=NN && !used[x]);
}
void solve(int N)
{
NN=N;
int low = 1;
int high = N-1;
int res = 1;
while(low <= high)
{
int mid = (low+high)/2;
if(query(mid,N) == N-1)
{
res=max(res,mid);
low=mid+1;
}
else
high=mid-1;
}
used[1] = true;
A[res] = 1;
for(int i = res-1;i >= 1;i --)
{
int dif1 = query(i,i+1);
if(!is_valid(A[i+1]+dif1))
A[i] = A[i+1]-dif1;
else if(!is_valid(A[i+1]-dif1))
A[i] = A[i+1]+dif1;
else
{
int dif2 = query(i,i+2);
if(A[i+1] < A[i+2])
{
if(dif2 == A[i+2]-A[i+1])
A[i] = dif1+A[i+1];
else if(dif2 > dif1)
A[i] = dif1+A[i+1];
else
A[i] = A[i+1]-dif1;
}
else
{
if(dif2 == A[i+1]-A[i+2])
A[i] = A[i+1]-dif1;
else if(dif2 > dif1)
A[i] = A[i+1]+dif1;
else
A[i] = A[i+1]-dif1;
}
}
used[A[i]] = true;
}
for(int i = res+1;i <= N;i++)
{
int dif1 = query(i-1,i);
if(!is_valid(A[i-1]+dif1))
A[i] = A[i-1]-dif1;
else if(!is_valid(A[i-1]-dif1))
A[i] = A[i-1]+dif1;
else
{
int dif2 = query(i-2,i);
if(A[i-1] < A[i-2])
{
if(dif2 == A[i-2]-A[i-1])
A[i] = dif1+A[i-1];
else if(dif2 > dif1)
A[i] = dif1+A[i-1];
else
A[i] = A[i-1]-dif1;
}
else
{
if(dif2 == A[i-1]-A[i-2])
A[i] = A[i-1]-dif1;
else if(dif2 > dif1)
A[i] = A[i-1]+dif1;
else
A[i] = A[i-1]-dif1;
}
}
used[A[i]] = true;
}
for(int i = 1;i <= N;i++)
answer(i,A[i]);
return;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Runtime error |
5 ms |
512 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 |
4 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Runtime error |
5 ms |
512 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 |
4 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |