| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 654547 | anhduc2701 | Xylophone (JOI18_xylophone) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "xylophone.h"
using namespace std;
typedef long long ll;
const ll INF=1e18;
const int maxn=1e6+5;
const int mod=1e9+7;
const int mo=998244353;
using pi=pair<ll,ll>;
using vi=vector<ll>;
using pii=pair<pair<ll,ll>,ll>;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI 3.14159265359
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
int n;
int a[5005];
int ok[10005];
signed main(){
cin>>n;
int l=1;
int r=n;
int pos;
while(l<=r){
int mid=(l+r)/2;
if(query(mid,n)>=n-1){
pos=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
a[pos]=1;
if(pos>1){
a[pos-1]=1+query(pos-1,pos);
a[pos+1]=1+query(pos,pos+1);
ok[a[pos-1]]=1;
ok[a[pos+1]]=1;
ok[1]=1;
for(int i=pos-2;i>=1;i--){
int hieu=query(i,i+1);
if(a[i+1]+hieu>n || ok[a[i+1]+hieu]==1){
a[i]=a[i+1]-hieu;
ok[a[i]]=1;
continue;
}
if(a[i+1]-hieu<1 || ok[a[i+1]-hieu]==1){
a[i]=a[i+1]+hieu;
ok[a[i]]=1;
continue;
}
int hieumoi=query(i,i+2);
int x1=a[i+2];
int y1=a[i+1];
if(y1>x1)swap(x1,y1);
if(hieumoi==x1-y1){
a[i]=y1+hieu;
ok[a[i]]=1;
}
if(hieumoi==x1-y1-hieu ){
a[i]=y1+hieu;
ok[a[i]]=1;
}
if(x1-y1+hieu==hieumoi ){
a[i]=y1+hieu;
ok[a[i]]=1;
}
}
}
if(pos<n){
for(int i=pos+2;i<=n;i++){
int hieu=query(i-1,i);
if(a[i-1]+hieu>n || ok[a[i-1]+hieu]==1){
a[i]=a[i-1]-hieu;
ok[a[i]]=1;
continue;
}
if(a[i-1]-hieu<1 || ok[a[i-1]-hieu]==1){
a[i]=a[i-1]+hieu;
ok[a[i]]=1;
continue;
}
int hieumoi=query(i-2,i);
int x1=a[i-2];
int y1=a[i-1];
if(y1>x1)swap(x1,y1);
if(hieumoi==x1-y1){
a[i]=y1+hieu;
ok[a[i]]=1;
}
if(hieumoi==x1-y1-hieu ){
a[i]=y1+hieu;
ok[a[i]]=1;
}
if(x1-y1+hieu==hieumoi ){
a[i]=y1+hieu;
ok[a[i]]=1;
}
}
}
for(int i=1;i<=n;i++){
answer(i,a[i]);
}
}