#include <bits/stdc++.h>
using namespace std;
#include "xylophone.h"
void solve(int n){
int lo=1,hi=n-1,mid;
while(lo<hi){
mid=(lo+hi+1)/2;
int x=query(mid,n);
if(x==n-1) lo=mid;
else hi=mid-1;
}
int ans[n+1];
memset(ans,-1,sizeof(ans));
ans[lo]=1;
if(lo>1) ans[lo-1]=1+query(lo-1,lo);
for(int i=lo-2; i>0; i--){
int x=query(i,i+2);
if(min(ans[i+1],ans[i+2])+x>=n) ans[i]=max(ans[i+1],ans[i+2])-x;
else if(max(ans[i+1],ans[i+2])-x<1) ans[i]=min(ans[i+1],ans[i+2])+x;
else{
if(x==max(ans[i+1],ans[i+2])-min(ans[i+1],ans[i+2])){
if(ans[i+1]<ans[i+2]) ans[i]=ans[i+1]+query(i,i+1);
else ans[i]=ans[i+1]-query(i,i+1);
}
else{
int y=query(i,i+1);
if(ans[i+1]+y==min(ans[i+1],ans[i+2])+x) ans[i]=ans[i+1]+y;
else ans[i]=ans[i+1]-y;
}
}
}
ans[lo+1]=1+query(lo,lo+1);
for(int i=lo+2; i<=n; i++){
int x=query(i-2,i);
if(min(ans[i-1],ans[i-2])+x>n) ans[i]=max(ans[i-1],ans[i-2])-x;
else if(max(ans[i-1],ans[i-2])-x<1) ans[i]=min(ans[i-1],ans[i-2])+x;
else{
if(x==max(ans[i-1],ans[i-2])-min(ans[i-1],ans[i-2])){
if(ans[i-1]<ans[i-2]) ans[i]=ans[i-1]+query(i-1,i);
else ans[i]=ans[i-1]-query(i-1,i);
}
else{
int y=query(i-1,i);
if(ans[i-1]+y==min(ans[i-1],ans[i-2])+x) ans[i]=ans[i-1]+y;
else ans[i]=ans[i-1]-y;
}
}
}
for(int i=1; i<=n; i++) answer(i,ans[i]);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
2 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
2 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
2 ms |
344 KB |
Output is correct |
17 |
Correct |
6 ms |
344 KB |
Output is correct |
18 |
Correct |
9 ms |
432 KB |
Output is correct |
19 |
Correct |
8 ms |
344 KB |
Output is correct |
20 |
Correct |
8 ms |
344 KB |
Output is correct |
21 |
Correct |
9 ms |
440 KB |
Output is correct |
22 |
Correct |
11 ms |
348 KB |
Output is correct |
23 |
Correct |
10 ms |
344 KB |
Output is correct |
24 |
Correct |
10 ms |
344 KB |
Output is correct |
25 |
Correct |
14 ms |
436 KB |
Output is correct |
26 |
Correct |
12 ms |
344 KB |
Output is correct |
27 |
Correct |
12 ms |
344 KB |
Output is correct |
28 |
Correct |
8 ms |
344 KB |
Output is correct |
29 |
Correct |
11 ms |
436 KB |
Output is correct |
30 |
Correct |
9 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
2 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
2 ms |
344 KB |
Output is correct |
17 |
Correct |
6 ms |
344 KB |
Output is correct |
18 |
Correct |
9 ms |
432 KB |
Output is correct |
19 |
Correct |
8 ms |
344 KB |
Output is correct |
20 |
Correct |
8 ms |
344 KB |
Output is correct |
21 |
Correct |
9 ms |
440 KB |
Output is correct |
22 |
Correct |
11 ms |
348 KB |
Output is correct |
23 |
Correct |
10 ms |
344 KB |
Output is correct |
24 |
Correct |
10 ms |
344 KB |
Output is correct |
25 |
Correct |
14 ms |
436 KB |
Output is correct |
26 |
Correct |
12 ms |
344 KB |
Output is correct |
27 |
Correct |
12 ms |
344 KB |
Output is correct |
28 |
Correct |
8 ms |
344 KB |
Output is correct |
29 |
Correct |
11 ms |
436 KB |
Output is correct |
30 |
Correct |
9 ms |
344 KB |
Output is correct |
31 |
Correct |
17 ms |
412 KB |
Output is correct |
32 |
Correct |
27 ms |
424 KB |
Output is correct |
33 |
Correct |
29 ms |
424 KB |
Output is correct |
34 |
Correct |
44 ms |
436 KB |
Output is correct |
35 |
Correct |
51 ms |
432 KB |
Output is correct |
36 |
Incorrect |
55 ms |
344 KB |
Wrong Answer [2] |
37 |
Halted |
0 ms |
0 KB |
- |