Submission #70789

#TimeUsernameProblemLanguageResultExecution timeMemory
70789dnassXylophone (JOI18_xylophone)C++14
100 / 100
82 ms704 KiB
#include "xylophone.h" #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n; int a[5010]; bool found[5010]; int place_1, place_n; int bin_search_n(int l, int r){ if(l==r) return l; if(l+1==r){ int x = query(1, r); if(x==n-1) return r; else return l; } int mid = (l+r)/2; int x = query(1, mid); if(x<n-1) return bin_search_n(mid+1, r); else return bin_search_n(l, mid); } int bin_search_1(int l, int r){ if(l==r) return l; if(l+1==r){ int x = query(r, n); if(x==n-1) return r; else return l; } int mid = (l+r)/2; int x = query(mid, n); if(x<n-1) return bin_search_1(l, mid-1); else return bin_search_1(mid, r); } void solve(int N) { n = N; memset(found, false, sizeof found); //place_n = bin_search_n(1, n); a[place_n] = n; found[n] = true; place_1 = bin_search_1(1, n); a[place_1] = 1; found[1] = true; for(int i=place_1-1;i>0;i--){ int x = query(i, i+1); int mx = a[i+1]+x, mn = a[i+1]-x; if(mx>n||found[mx]){ a[i] = mn; found[mn] = true; }else if(mn<1||found[mn]){ a[i] = mx; found[mx] = true; }else{ int y = query(i, i+2); if(a[i+2]>a[i+1]){ if(y==a[i+2]-mn){ a[i] = mn; found[mn] = true; }else{ a[i] = mx; found[mx] = true; } }else{ if(y==mx-a[i+2]){ a[i] = mx; found[mx] = true; }else{ a[i] = mn; found[mn] = true; } } } } for(int i=place_1+1;i<=n;i++){ //if(i==place_n) continue; int x = query(i-1, i); int mx = a[i-1]+x, mn = a[i-1]-x; //printf("a[i-1]: %d, mn: %d, mx: %d\n", a[i-1], mn, mx); if(mx>n||found[mx]){ a[i] = mn; found[mn] = true; }else if(mn<1||found[mn]){ a[i] = mx; found[mx] = true; }else{ int y = query(i-2, i); if(a[i-2]>a[i-1]){ if(y==a[i-2]-mn){ a[i] = mn; found[mn] = true; }else{ a[i] = mx; found[mx] = true; } }else{ if(y==mx-a[i-2]){ a[i] = mx; found[mx] = true; }else{ a[i] = mn; found[mn] = true; } } } } for(int i=1;i<=n;i++){ //printf("%d ", a[i]); answer(i, a[i]); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...