Submission #653309

#TimeUsernameProblemLanguageResultExecution timeMemory
653309Dec0DeddXylophone (JOI18_xylophone)C++14
0 / 100
1 ms208 KiB
#include <bits/stdc++.h> #include "xylophone.h" using namespace std; const int N = 5e3+1; int ans[N], n; bool us[N]; // [i, j, k] int que(int l, int r) { return query(min(l, r), max(l, r)); } int val(int i, int j, int k) { int l=que(i, j), res=0; if (ans[j]+l > n || us[ans[j]+l]) res=ans[j]-l; else if (ans[j]-l < 1 || us[ans[j]-l]) res=ans[j]+l; else { int p=query(k, i); int y=ans[k], a=ans[j]; assert(y != a+l), assert(y != a-l); if (y > a+l) { if (p == y-a) res=a+l; else res=a-l; } else if (y > a && y < a+l) { if (p == l) res=a+l; else res=a-l; } else if (y < a && y > a-l) { if (p == l) res=a-l; else res=a+l; } else if (y < a-l) { if (p == a-y) res=a-l; else res=a+l; } } return res; } void solve(int np) { n=np; int l=1, r=n, x=1; while (l <= r) { int m=(l+r)/2; if (que(1, m) == n-1) r=m-1, x=m; else l=m+1; } ans[x]=n; if (x < n) ans[x+1]=n-query(x, x+1); if (x > 1) ans[x-1]=n-query(x-1, x); for (int i=x+2; i<=n; ++i) { int l=que(i-1, i); if (ans[i-1]+l > n || us[ans[i-1]+l]) ans[i]=ans[i-1]-l; else if (ans[i-1]-l < 1 || us[ans[i-1]-l]) ans[i]=ans[i-1]+l; else ans[i]=val(i, i-1, i-2); us[ans[i]]=true; } for (int i=x-2; i>=1; --i) { int l=que(i, i+1); if (ans[i+1]+l > n || us[ans[i+1]+l]) ans[i]=ans[i+1]-l; else if (ans[i+1]-l < 1 || us[ans[i+1]-l]) ans[i]=ans[i+1]+l; else ans[i]=val(i, i+1, i+2); us[ans[i]]=true; } for (int i=1; i<=n; ++i) { assert(ans[i] > 0); answer(i, ans[i]); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...