Submission #1220097

#TimeUsernameProblemLanguageResultExecution timeMemory
1220097akqxolotlXylophone (JOI18_xylophone)C++20
47 / 100
24 ms428 KiB
#include "xylophone.h" static int A[5000]; #include <bits/stdc++.h> using namespace std; #define debug(x) cerr<<#x<<" is "<<x<<endl; /*typedef pair<int,int> pii; #define fi first #define se second*/ void solve(int n) { int l=1,h=n; while(l<h-1){ int m=(l+h)/2; //debug(m) int q=query(m,n); //debug(q) if(q<n-1)h=m; else l=m; } int a[n+1]; int mi=l; //debug(mi) a[mi]=1; if(mi>1)a[mi-1]=query(mi-1,mi)+1; a[mi+1]=query(mi,mi+1)+1; for(int i=mi-2;i>0;i--){ //debug(1) int q1=query(i,i+1); int q2=query(i,i+2); int c1=a[i+1]+q1; int c2=a[i+1]-q1; if(q1+abs(a[i+1]-a[i+2])==q2){//sorted order if(a[i+2]>a[i+1])a[i]=c2;//desc else a[i]=c1; }else{ if(a[i+2]>a[i+1])a[i]=c1; else a[i]=c2; } } for(int i=mi+2;i<=n;i++){ //debug(2) int q1=query(i-1,i); int q2=query(i-2,i); int c1=a[i-1]+q1; int c2=a[i-1]-q1; if(q1+abs(a[i-1]-a[i-2])==q2){ if(a[i-2]<a[i-1])a[i]=c1;//asc else a[i]=c2; }else{ if(a[i-2]<a[i-1])a[i]=c2; else a[i]=c1; } } for(int i=1;i<=n;i++){ //cerr<<a[i]<<' '; answer(i,a[i]); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...