oj.uz

Submission #1046714

# Submission time Handle Problem Language Result Execution time Memory
1046714 2024-08-06T20:53:31 Z pera Xylophone (JOI18_xylophone) C++17
0 / 100
 1 ms 344 KB 
#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] + v;
         }else{
            if(u < v){
               A[i] = A[i - 1] - v;
            }else{
               A[i] = A[i - 2] + u;
            }
         }
      }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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -