제출 #516507

#제출 시각아이디문제언어결과실행 시간메모리
516507drkarlicio2107Xylophone (JOI18_xylophone)C++14
0 / 100
1 ms200 KiB
#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 (int 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]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...