# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
111331 | 2019-05-14T19:51:55 Z | vex | Xylophone (JOI18_xylophone) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h> #include<xylophone.h> using namespace std; int d1[5005]; int d2[5005]; int zn[5005]; void solve(int n) { for(int i=1;i<n;i++)d1[i]=query(i,i+1); for(int i=1;i<n-1;i++)d2[i]=query(i,i+2); zn[1]=1; for(int i=2;i<n-1;i++) { if(d1[i-1]+d1[i]==d2[i-1])zn[i]=zn[i-1]; else zn[i]=-zn[i-1]; } int tre=0; int minv=0;int minn=1; int maxv=0;int maxx=1; for(int i=2;i<=n;i++) { tre+=d1[i-1]*zn[i-1]; if(tre>maxv) { maxv=tre; maxx=i; } if(tre<minv) { minv=tre; minn=i; } } int sgn=1; if(minn>maxx) { sgn=-sgn; swap(minn,maxx); } a[minn]=1; for(int i=minn+1;i<=n;i++)a[i]=a[i-1]+sgn*d1[i-1]*zn[i-1]; for(int i=minn-1;i>0;i--)a[i]=a[i+1]-sgn*d1[i]*zn[i]; for(int i=1;i<=n;i++)answer(i,a[i]); }