#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define F first
#define S second
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define maxp 22
#define EPS (ld)(1e-18)
#define mod (int)(1e9+7)
int asked[5001][5001];
int ask(int l, int r){
if(asked[l][r]!=-1)
return asked[l][r];
asked[l][r]=query(l,r);
return asked[l][r];
}
void solve(int N) {
int arr[N+1];
int i,j;
for(i=0;i<=N;i++)
for(j=0;j<=N;j++)
asked[i][j]=-1;
int l=1,r=N;
while(l<r){
int mid=(l+r)/2;
int x=ask(1,mid);
if(x==N-1)
r=mid-1;
else
l=mid+1;
}
int found;
int x=ask(1,l);
if(x==N-1)
found=l;
else
found=l+1;
//cout<<found<<endl;
arr[found]=N;
if(found>1){
int x=ask(found-1,found);
arr[found-1]=N-x;
}
if(found<N){
int x=ask(found,found+1);
arr[found+1]=N-x;
}
for(i=found-2;i>=1;i--){
int x2=ask(i,i+1);
int x3=ask(i,i+2);
int p1=arr[i+1]-x2;
int p2=arr[i+1]+x2;
if(max({p1,arr[i+1],arr[i+2]})-min({p1,arr[i+1],arr[i+2]})==x3)
arr[i]=p1;
else
arr[i]=p2;
}
for(i=found+2;i<=N;i++){
int x2=ask(i-1,i);
int x3=ask(i-2,i);
int p1=arr[i-1]-x2;
int p2=arr[i-1]+x2;
if(max({p1,arr[i-1],arr[i-2]})-min({p1,arr[i-1],arr[i-2]})==x3)
arr[i]=p1;
else
arr[i]=p2;
}
for(i=1;i<=N;i++)
answer(i,arr[i]);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
256 KB |
Output is correct |
3 |
Correct |
5 ms |
512 KB |
Output is correct |
4 |
Correct |
7 ms |
768 KB |
Output is correct |
5 |
Correct |
6 ms |
768 KB |
Output is correct |
6 |
Correct |
6 ms |
768 KB |
Output is correct |
7 |
Correct |
6 ms |
768 KB |
Output is correct |
8 |
Correct |
6 ms |
768 KB |
Output is correct |
9 |
Correct |
7 ms |
768 KB |
Output is correct |
10 |
Correct |
6 ms |
768 KB |
Output is correct |
11 |
Correct |
7 ms |
640 KB |
Output is correct |
12 |
Correct |
7 ms |
768 KB |
Output is correct |
13 |
Correct |
6 ms |
768 KB |
Output is correct |
14 |
Correct |
6 ms |
768 KB |
Output is correct |
15 |
Correct |
7 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
256 KB |
Output is correct |
3 |
Correct |
5 ms |
512 KB |
Output is correct |
4 |
Correct |
7 ms |
768 KB |
Output is correct |
5 |
Correct |
6 ms |
768 KB |
Output is correct |
6 |
Correct |
6 ms |
768 KB |
Output is correct |
7 |
Correct |
6 ms |
768 KB |
Output is correct |
8 |
Correct |
6 ms |
768 KB |
Output is correct |
9 |
Correct |
7 ms |
768 KB |
Output is correct |
10 |
Correct |
6 ms |
768 KB |
Output is correct |
11 |
Correct |
7 ms |
640 KB |
Output is correct |
12 |
Correct |
7 ms |
768 KB |
Output is correct |
13 |
Correct |
6 ms |
768 KB |
Output is correct |
14 |
Correct |
6 ms |
768 KB |
Output is correct |
15 |
Correct |
7 ms |
768 KB |
Output is correct |
16 |
Correct |
9 ms |
1408 KB |
Output is correct |
17 |
Correct |
15 ms |
3200 KB |
Output is correct |
18 |
Correct |
20 ms |
6328 KB |
Output is correct |
19 |
Correct |
24 ms |
8300 KB |
Output is correct |
20 |
Correct |
24 ms |
8308 KB |
Output is correct |
21 |
Correct |
23 ms |
8312 KB |
Output is correct |
22 |
Correct |
25 ms |
8192 KB |
Output is correct |
23 |
Correct |
26 ms |
8320 KB |
Output is correct |
24 |
Correct |
27 ms |
8324 KB |
Output is correct |
25 |
Correct |
24 ms |
8320 KB |
Output is correct |
26 |
Correct |
27 ms |
8320 KB |
Output is correct |
27 |
Correct |
18 ms |
8328 KB |
Output is correct |
28 |
Correct |
24 ms |
8320 KB |
Output is correct |
29 |
Correct |
18 ms |
8352 KB |
Output is correct |
30 |
Correct |
26 ms |
8320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
256 KB |
Output is correct |
3 |
Correct |
5 ms |
512 KB |
Output is correct |
4 |
Correct |
7 ms |
768 KB |
Output is correct |
5 |
Correct |
6 ms |
768 KB |
Output is correct |
6 |
Correct |
6 ms |
768 KB |
Output is correct |
7 |
Correct |
6 ms |
768 KB |
Output is correct |
8 |
Correct |
6 ms |
768 KB |
Output is correct |
9 |
Correct |
7 ms |
768 KB |
Output is correct |
10 |
Correct |
6 ms |
768 KB |
Output is correct |
11 |
Correct |
7 ms |
640 KB |
Output is correct |
12 |
Correct |
7 ms |
768 KB |
Output is correct |
13 |
Correct |
6 ms |
768 KB |
Output is correct |
14 |
Correct |
6 ms |
768 KB |
Output is correct |
15 |
Correct |
7 ms |
768 KB |
Output is correct |
16 |
Correct |
9 ms |
1408 KB |
Output is correct |
17 |
Correct |
15 ms |
3200 KB |
Output is correct |
18 |
Correct |
20 ms |
6328 KB |
Output is correct |
19 |
Correct |
24 ms |
8300 KB |
Output is correct |
20 |
Correct |
24 ms |
8308 KB |
Output is correct |
21 |
Correct |
23 ms |
8312 KB |
Output is correct |
22 |
Correct |
25 ms |
8192 KB |
Output is correct |
23 |
Correct |
26 ms |
8320 KB |
Output is correct |
24 |
Correct |
27 ms |
8324 KB |
Output is correct |
25 |
Correct |
24 ms |
8320 KB |
Output is correct |
26 |
Correct |
27 ms |
8320 KB |
Output is correct |
27 |
Correct |
18 ms |
8328 KB |
Output is correct |
28 |
Correct |
24 ms |
8320 KB |
Output is correct |
29 |
Correct |
18 ms |
8352 KB |
Output is correct |
30 |
Correct |
26 ms |
8320 KB |
Output is correct |
31 |
Correct |
53 ms |
27392 KB |
Output is correct |
32 |
Correct |
85 ms |
50040 KB |
Output is correct |
33 |
Correct |
113 ms |
85752 KB |
Output is correct |
34 |
Incorrect |
141 ms |
98168 KB |
Wrong Answer [2] |
35 |
Halted |
0 ms |
0 KB |
- |