# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
516535 | drkarlicio2107 | Xylophone (JOI18_xylophone) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
int bio [5010]; int l [5010];
int moze (int x, int n){
if (bio[x] || x>n || x<1) return 0;
return 1;
}
int moze2 (int x, int y, int diff1, int diff2){
int z1=y+diff1, z2=y-diff1;
if (max (abs(x-y), max(abs (x-z1), abs (y-z1)))==diff2) return z1;
return z2;
}
void solve (int n){
int lo=1; int hi=n;
while (hi-lo>1){
//cout << lo << " " << hi;
int mid=(lo+hi)/2;
int x=query (mid, n);
if (x==n-1) lo=mid;
else hi=mid-1;
}
if (hi!=lo){
if (query (hi, n)==n-1) lo++;
}
//cout << lo;
bio [1]=1; l[lo]=1;
for (int i=lo+1; i<n+1; i++){
int x=query (i-1, i);
if (moze (l[i-1]+x) && moze (l[i-1]-x)){
int y=query (i-2, i);
l[i]=moze2 (l[i-2], l[i-1], x, y); bio [moze2 (l[i-2], l[i-1], x, y)]=1;
}
else{
if (moze(l[i-1]+x)){
l[i]=l[i-1]+x; bio [l[i-1]+x]=1;
}
else{
l[i]=l[i-1]-x; bio [l[i-1]-x]=1;
}
}
}
for (int i=lo-1; i>0; i--){
int x=query (i, i+1);
if (moze (l[i+1]+x) && moze (l[i+1]-x)){
int y=query (i, i+2);
if (y>abs(l[i+1]-l[i+2])){
int y=query (i+2, i);
l[i]=moze2 (l[i+2], l[i+1], x, y); bio [moze2 (l[i+2], l[i+1], x, y)]=1;
}
else{
if (l[i+1]>l[i+2]){
l[i]=l[i+1]-x; bio [l[i+1]-x]=1;
}
else{
l[i]=l[i+1]+x; bio [l[i+1]+x]=1;
}
}
}
else{
if (moze(l[i+1]+x)){
l[i]=l[i+1]+x; bio [l[i+1]+x]=1;
}
else{
l[i]=l[i+1]-x; bio [l[i+1]-x]=1;
}
}
}
for (int i=1; i<n+1; i++) answer (i, l[i]);
}