Submission #996130

#TimeUsernameProblemLanguageResultExecution timeMemory
996130vjudge1Xylophone (JOI18_xylophone)C++14
0 / 100
0 ms344 KiB
/* Soln: Find position of 1 using binary search query(i,N) == N-1 After that solve left and right parts individually For left part for example, A[i-1] can be easily found by 1 query For A[j], j <= i-2, you may require 1 or 2 queries Check abs(A[j+1]-A[j]). You get 2 possible values of A[j] If one of the values has already been put somewhere then we don't need any more queries Otherwise query(j,j+2) for finding exact value. This is <= 2n+log(n) queries for sure but not sure why it takes <= 2n queries(or maybe it doesn't and test cases are weak) Logically thinking it is intuitive it should take much less steps but Idk formal proof. */ #include "xylophone.h" #include<bits/stdc++.h> using namespace std; #define REP(i,n) for(int i = 0; i < n; i ++) static int A[5005]; int pos[5005]; void solve(int n) { if(n==1){ answer(1,1); } else if(n==2){ answer(1,1); answer(1,2); } else{ int diff2[n+1]; int diff1[n+1]; for(int i=3;i<=n;i++){ diff1[i]=query(i-1,i); diff2[i]=query(i-2,i); } int a[n+1]; int dist=query(1,2); for(int m=-1;m<=1;m+=2){ a[1]=1e9; a[2]=a[1]+m*dist; int Min=min(a[1],a[2]); for(int i=3;i<=n;i++){ if(diff2[i]==diff1[i]+abs(a[i-2]-a[i-1])){ if(a[i-2]>a[i-1]){ a[i]=a[i-1]-diff1[i]; } else{ a[i]=a[i-1]+diff1[i]; } } else{ if(a[i-2]>a[i-1]){ a[i]=a[i-1]+diff1[i]; } else{ a[i]=a[i-1]-diff1[i]; } } Min=min(a[1],a[i]); } Min--; bool mark[n+1]={false}; bool flag=true; for(int i=1;i<=n;i++){ a[i]-=Min; if(a[i]>n||a[i]<=1||mark[a[i]]){ flag=false; break; } mark[a[i]]=true; } if(flag){ for(int i=1;i<=n;i++){ answer(i,a[i]); } } } } }

Compilation message (stderr)

xylophone.cpp:25:12: warning: 'A' defined but not used [-Wunused-variable]
   25 | static int A[5005];
      |            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...