| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 516504 | 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 n; int l [5010];
int moze (int x){
if (bio[x] || x>n || x<1) return 0;
return 1;
}
void solve (){
cin >> n;
int lo=1; int hi=n;
while (hi-lo>1){
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)) 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);
if (y>abs(l[i-1]-l[i-2])){
if (l[i-1]>l[i-2]){
l[i]=l[i-2]+y; bio [l[i-2]+y]=1;
}
else{
l[i]=l[i-2]-y; bio [l[i-2]-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=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])){
if (l[i+1]>l[i+2]){
l[i]=l[i+2]+y; bio [l[i+2]+y]=1;
}
else{
l[i]=l[i+2]-y; bio [l[i+2]-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]);
}