This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;
int res[N + 1];
void solve(int n) {
int l = 1,r = n,tr;
int pos;
while(l < r) {
int mid = (l + r)/2;
if(query(mid,n) >= n - 1) {
l = mid + 1;
pos = mid;
} else {
r = mid;
}
}
res[pos] = 1;
for(int i = pos - 1;i >= 1;i--) {
int w = query(i,i + 1);
if(res[i + 1] + w > n) {
res[i] = res[i + 1] - w;
continue;
}
if(res[i + 1] <= w) {
res[i] = res[i + 1] + w;
continue;
}
vector<int> st = {res[i + 1],res[i + 2]};
sort(st.begin(),st.end());
int asd = query(i,i + 2);
if(asd == st[1] - st[0]) {
if(res[i + 1] == st[0]) {
res[i] = res[i + 1] + w;
} else {
res[i] = res[i + 1] - w;
}
} else {
if(asd == w) {
if(res[i + 1] == st[0]) {
res[i] = res[i + 1] + w;
} else {
res[i] = res[i + 1] - w;
}
} else {
if(res[i + 2] == st[0]) {
res[i] = res[i + 2] + asd;
} else {
res[i] = res[i + 2] - asd;
}
}
}
}
for(int i = pos + 1;i <= n;i++) {
int w = query(i - 1,i);
if(res[i - 1] <= w) {
res[i] = res[i - 1] + w;
continue;
}
if(res[i - 1] + w > n) {
res[i] = res[i - 1] - w;
continue;
}
vector<int> st = {res[i - 1],res[i - 2]};
sort(st.begin(),st.end());
int asd = query(i - 2,i);
if(asd == st[1] - st[0]) {
if(res[i - 1] == st[0]) {
res[i] = res[i - 1] + w;
} else {
res[i] = res[i - 1] - w;
}
} else {
if(asd == w) {
if(res[i - 1] == st[0]) {
res[i] = res[i - 1] + w;
} else {
res[i] = res[i - 1] - w;
}
} else {
if(res[i - 2] == st[0]) {
res[i] = res[i - 2] + asd;
} else {
res[i] = res[i - 2] - asd;
}
}
}
}
for(int i = 1;i <= n;i++) {
answer(i,res[i]);
}
return;
}
Compilation message (stderr)
xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:10:18: warning: unused variable 'tr' [-Wunused-variable]
10 | int l = 1,r = n,tr;
| ^~
xylophone.cpp:11:6: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
11 | int pos;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |