Submission #1046709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046709		pera	Xylophone (JOI18_xylophone)	C++17	0 / 100	1 ms	344 KiB

xylophone

#include<bits/stdc++.h>
#include "xylophone.h"
using namespace std;
void solve(int N){
   vector<int> A(N + 1) , e(N + 1);
   int x = 0 , y = 0;
   for(int bit = 12;bit >= 0;bit --){
      if(y + (1 << bit) <= N){
         if(query(1 , y + (1 << bit)) < N - 1){
            y += (1 << bit);
         }
      }
   }
   ++y;
   for(int bit = 12;bit >= 0;bit --){
      if(x + (1 << bit) <= y){
         if(query(x + (1 << bit) , y) == N - 1){
            x += (1 << bit);
         }
      }
   }
   e[1] = 1;
   e[N] = 1;
   A[x] = 1;
   A[y] = N;
   auto bad = [&](int v){
      if(v < 1 || v > N){
        return 1;
      } 
      return e[v];
   };
   for(int i = x - 1;i >= 1;i --){
      int v = query(i , i + 1);
      if(bad(A[i + 1] - v)){
         A[i] = A[i + 1] + v;
         e[A[i]] = 1;
         continue;
      }
      if(bad(A[i + 1] + v)){
         A[i] = A[i + 1] - v;
         e[A[i]] = 1;
         continue;
      }
      int u = query(i , i + 2);
      if(A[i + 1] < A[i + 2]){
         if(u + v == A[i + 2] - A[i + 1]){
            A[i] = A[i + 1] + u;
         }else{
            if(u < v){
               A[i] = A[i + 1] - u;
            }else{
               A[i] = A[i + 2] + v;
            }
         }
      }else{
         if(u + v == A[i + 1] - A[i + 2]){
            A[i] = A[i + 2] + v;
         }else{
            if(v < u){
               A[i] = A[i + 2] - v;
            }else{
               A[i] = A[i + 1] + u;
            }
         }
      }
      e[A[i]] = 1;
   }
   for(int i = x + 1;i <= N;i ++){
      if(i == y){
         continue;
      }
      int v = query(i - 1 , i);
      if(bad(A[i - 1] - v)){
         A[i] = A[i - 1] + v;
         e[A[i]] = 1;
         continue;
      }
      if(bad(A[i - 1] + v)){
         A[i] = A[i - 1] - v;
         e[A[i]] = 1;
         continue;
      }
      int u = query(i - 2 , i);
      if(A[i - 1] < A[i - 2]){
         if(u + v == A[i - 2] - A[i - 1]){
            A[i] = A[i - 1] + u;
         }else{
            if(u < v){
               A[i] = A[i - 1] - u;
            }else{
               A[i] = A[i - 2] + v;
            }
         }
      }else{
         if(u + v == A[i - 1] - A[i - 2]){
            A[i] = A[i - 2] + v;
         }else{
            if(v < u){
               A[i] = A[i - 2] - v;
            }else{
               A[i] = A[i - 1] + u;
            }
         }
      }
      e[A[i]] = 1;
   }
   for(int i = 1;i <= N;i ++){
      answer(i , A[i]);
   }
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 36
• Subtask 3: 0 / 53