제출 #232827

#제출 시각아이디문제언어결과실행 시간메모리
232827Charis02Xylophone (JOI18_xylophone)C++14
0 / 100
5 ms512 KiB
#include "xylophone.h" #include<iostream> using namespace std; int A[5001]; bool used[5001]; int NN; bool is_valid(int x) { return (1 <= x && x<=NN && !used[x]); } void solve(int N) { NN=N; int low = 1; int high = N-1; int res = 1; while(low <= high) { int mid = (low+high)/2; if(query(mid,N) == N-1) { res=max(res,mid); low=mid+1; } else high=mid-1; } used[1] = true; A[res] = 1; for(int i = res-1;i >= 1;i --) { int dif1 = query(i,i+1); if(!is_valid(A[i+1]+dif1)) A[i] = A[i+1]-dif1; else if(!is_valid(A[i+1]-dif1)) A[i] = A[i+1]+dif1; else { int dif2 = query(i,i+2); if(A[i+1] < A[i+2]) { if(dif2 == A[i+2]-A[i+1]) A[i] = dif1+A[i+1]; else if(dif2 > dif1) A[i] = dif1+A[i+1]; else A[i] = A[i+1]-dif1; } else { if(dif2 == A[i+1]-A[i+2]) A[i] = A[i+1]-dif1; else if(dif2 > dif1) A[i] = A[i+1]+dif1; else A[i] = A[i+1]-dif1; } } used[A[i]] = true; } for(int i = res+1;i <= N;i++) { int dif1 = query(i-1,i); if(!is_valid(A[i-1]+dif1)) A[i] = A[i-1]-dif1; else if(!is_valid(A[i-1]-dif1)) A[i] = A[i-1]+dif1; else { int dif2 = query(i-2,i); if(A[i-1] < A[i-2]) { if(dif2 == A[i-2]-A[i-1]) A[i] = dif1+A[i-1]; else if(dif2 > dif1) A[i] = dif1+A[i-1]; else A[i] = A[i-1]-dif1; } else { if(dif2 == A[i-1]-A[i-2]) A[i] = A[i-1]-dif1; else if(dif2 > dif1) A[i] = A[i-1]+dif1; else A[i] = A[i-1]-dif1; } } used[A[i]] = true; } for(int i = 1;i <= N;i++) answer(i,A[i]); return; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...