Submission #57633

#	Time	Username	Problem	Language	Result	Execution time	Memory
57633		ruhanhabib39	Xylophone (JOI18_xylophone)	C++17	0 / 100	4 ms	772 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>

namespace {
   using namespace std;
   int A[5000 + 10];
   map<int,int> q[5000 + 10];
   int N;

   int ask(int l, int r) {
      if(l > r) swap(l, r);
      if(q[l].count(r)) return q[l][r];
      return q[l][r] = query(l, r);
   }
   int get1() {
      int lo = 1, hi = N;
      while(lo < hi) {
         int m = (lo + hi + 1) / 2;
         if(ask(m, N) == N-1) lo = m;
         else hi = m-1;
      }
      return lo;
   }
   void work(int dx, bool lt, int l, int r) {
      memset(A, 0, sizeof A);
      int i = dx == +1 ? l : r;
      int x = dx == +1 ? l : r;
      for(; l <= i+dx && i+dx <= r; i += dx) {
         if(ask(x, i) < ask(x, i+dx) && (x == i || ask(x, i+dx) != ask(i, i+dx))) {
            if(lt) A[i+dx] = A[x] + ask(x, i+dx);
            else A[i+dx] = A[x] - ask(x, i+dx);
            x = i;
         } else {
            x = i;
            lt ^= true;
            if(lt) A[i+dx] = A[x] + ask(x, i+dx);
            else A[i+dx] = A[x] - ask(x, i+dx);
         }
      }
   }
   int cc[5000 + 10];
   int AA[5000 + 10];

   bool yay(int x) {
      memset(cc, 0, sizeof cc);
      for(int i = 1; i <= N; i++) {
         AA[i] = A[i] + x;
         if(AA[i] < 1 || AA[i] > N) return false;
         cc[AA[i]]++;
      }
      for(int i = 1; i <= N; i++) {
         if(cc[i] != 1) return false;
      }
      int a = 1;
      while(AA[a] != 1) a++;
      int b = 1;
      while(AA[b] != N) b++;
      if(a > b) return false;
      return true;
   }
   bool bad() {
      for(int x = 1; x <= N; x++) {
         if(yay(x)) {
            for(int i = 1; i <= N; i++) {
               A[i] = AA[i];
            }
            return false;
         }
      }
      return true;
   }
};

void solve(int N_) {
   N = N_;
   work(+1, true, 1, N);
   if(bad()) {
      work(+1, false, 1, N);
   } 
   for(int i = 1; i <= N; i++) {
      answer(i, A[i]);
   }
}

Compilation message (stderr)

xylophone.cpp:15:8: warning: 'int {anonymous}::get1()' defined but not used [-Wunused-function]
    int get1() {
        ^~~~

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