이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
void solve(int N) {
/*
int value = query(1, N);
for(int i = 1; i <= N; i++) {
answer(i, i);
}
*/
int low = 1,high = N;
// prefix
while(low != high){
int mid = (low+high)/2;
if(query(1,mid) == N-1){
high = mid;
}else low = mid+1;
}
int five = high;
low = 1, high = N;
while(low != high){
int mid = (low+high+1)/2;
if(query(mid,N) == N-1){
low = mid;
}else high = mid-1;
}
int one = low;
vector<int> A(N+1,0);
A[one] = 1;
A[five] = N;
//cerr<< low <<" "<<high<< '\n';
int prev = 1;
if(one > 1){
int q = query(one-1,one);
A[one-1] = 1+q;
prev = q;
}
for(int i=one-2;i>=1;i--){
int q = query(i,i+1);
int sq = query(i,one);
if(sq > prev){
A[i] = A[i+1]+q;
}else{
A[i] = A[i+1]-q;
}
prev = sq;
}
if(one+1 < five){
int q = query(one,one+1);
A[one+1] = 1+q;
prev = q;
}
for(int i=one+2;i<five;i++){
int q = query(i,i+1);
int sq = query(one,i);
if(sq > prev){
A[i] = A[i-1]+q;
}else{
A[i] = A[i-1]-q;
}
prev = sq;
}
for(int i = 1; i <= N; i++) {
cerr<<A[i] << ' ';
}cerr<<'\n';
if(five+1 <= N){
int q = query(five,five+1);
A[five+1] = N-q;
prev = q;
}
for(int i = 1; i <= N; i++) {
cerr<<A[i] << ' ';
}cerr<<'\n';
for(int i=five+2;i<=N;i++){
int q = query(i-1,i);
int sq = query(five,i);
if(sq > prev){
A[i] = A[i-1]-q;
}else{
A[i] = A[i-1]+q;
}
prev = sq;
}
for(int i = 1; i <= N; i++) {
cerr<<A[i] << ' ';
}cerr<<'\n';
for(int i = 1; i <= N; i++) {
answer(i, A[i]);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |