Submission #342206

#TimeUsernameProblemLanguageResultExecution timeMemory
342206bigDuckXylophone (JOI18_xylophone)C++14
0 / 100
0 ms364 KiB
#include<bits/stdc++.h> using namespace std; #define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define mp make_pair #define pb push_back #define ft first #define sc second #define ll long long #define pii pair<int, int> #define count_bits __builtin_popcount #include "xylophone.h" /* query(s, t); answer(i, a); */ int d[5010][2]; map<int, int> h; int a[5010]; int sgn[5010]; void solve(int N) { int n=N; if(n==2){ answer(1, 1); answer(2, N); return; } for(int i=2; i<=n; i++){ d[i][0]=query(i-1, i); if(i>2){ d[i][1]=query(i-2, i); } } //d[2][0]=|a2-a1| //pozitiv int f=0, l=0; bool ok=true; sgn[2]=+1; int sum=d[2][0]; h[0]=1; h[sum]=2; for(int i=3; i<=n; i++){ int d1=d[i-1][0], d2=d[i][0], d3=d[i][1]; if(d3==(d1+d2)){ sgn[i]=sgn[i-1]; } else{ if( (d3==(d1)) || (d3==(d2)) ){ sgn[i]=-sgn[i-1]; } } sum+=sgn[i]*d[i][0]; h[sum]=i; if(h[sum+(n-1)]!=0 ){ ok=false; break; } if(h[sum-(n-1) ]!=0){ f=h[sum-(n-1)]; l=i; } } if(ok){ a[f]=1; a[l]=N; a[f]=1; a[l]=N; for(int i=f-1; i>=1; i--){ a[i]=a[i+1]-sgn[i+1]*d[i+1][0]; } for(int i=f+1; i<=N; i++){ a[i]=a[i-1]+sgn[i]*d[i][0]; } for(int i=1; i<=n; i++){ answer(i, a[i]); } return; } h.clear(); sgn[2]=-1; sum=-d[2][0]; h[0]=1; h[sum]=2; for(int i=3; i<=n; i++){ int d1=d[i-1][0], d2=d[i][0], d3=d[i][1]; if(d3==(d1+d2)){ sgn[i]=sgn[i-1]; } else{ if( (d3==(d1)) || (d3==(d2)) ){ sgn[i]=-sgn[i-1]; } } sum+=sgn[i]*d[i][0]; h[sum]=i; if(h[sum-(n-1)]!=0 ){ f=h[sum-(n-1)], l=i; } } a[f]=1; a[l]=N; for(int i=f-1; i>=1; i--){ a[i]=a[i+1]-sgn[i+1]*d[i+1][0]; } for(int i=f+1; i<=N; i++){ a[i]=a[i-1]+sgn[i]*d[i][0]; } for(int i=1; i<=n; i++){ answer(i, a[i]); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...