Submission #951505

#	Time	Username	Problem	Language	Result	Execution time	Memory
951505		kilkuwu	Xylophone (JOI18_xylophone)	C++17	0 / 100	1 ms	432 KiB

xylophone

#include <bits/stdc++.h>

#ifndef LOCAL
#include "xylophone.h"
#else 
void solve(int N);
int query(int s, int t);
void answer(int i, int a);

static const int __N_MAX = 5000;
static const int __Q_MAX = 10000;
static int __N;
static int __A[__N_MAX];
static bool __used[__N_MAX];
static int __query_c;
static int __answer_c;

int query(int s, int t) {
	if(__query_c >= __Q_MAX) {
		printf("Wrong Answer\n");
		exit(0);
	}
	__query_c++;
	if(!(1 <= s && s <= t && t <= __N)) {
		printf("Wrong Answer\n");
		exit(0);
	}
	int mx = 0, mn = __N + 1;
	for(int i = s - 1; i < t; i++) {
		if(mx < __A[i]) {
			mx = __A[i];
		}
		if(mn > __A[i]) {
			mn = __A[i];
		}
	}
	return mx - mn;
}

void answer(int i, int a) {
	__answer_c++;
	if(!(1 <= i && i <= __N)) {
		printf("Wrong Answer\n");
		exit(0);
	}
	if(!(1 <= a && a <= __N)) {
		printf("Wrong Answer\n");
		exit(0);
	}
	if(__used[i - 1]) {
		printf("Wrong Answer\n");
		exit(0);
	}
	if(a != __A[i - 1]) {
		printf("Wrong Answer\n");
		exit(0);
	}
	__used[i - 1] = true;
}

int main() {
	__query_c = 0;
	__answer_c = 0;
	if(scanf("%d", &__N) != 1) {
		fprintf(stderr, "Error while reading input\n");
		exit(1);
	}
	for(int i = 0; i < __N; i++) {
		if(scanf("%d", __A + i) != 1) {
			fprintf(stderr, "Error while reading input\n");
			exit(1);
		}
		__used[i] = false;
	}
	solve(__N);
	if(!(__answer_c == __N)) {
		printf("Wrong Answer\n");
		exit(0);
	}
	printf("Accepted : %d\n", __query_c);
}

#endif

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

void solve(int N) {
  int lb = 1, rb = N;
  while (lb < rb) {
    int mid = (lb + rb + 1) / 2;
    if (query(mid, N) != N - 1) {
      rb = mid - 1;
    } else {
      lb = mid;
    }
  }

  // we know A[lb] == 1

  // we will know lb + 1
  
  std::vector<int> filled(N + 1, 0);
  std::vector<int> A(N + 1), D(N + 1, -1);
  A[lb] = 1;
  filled[1] = 1;

  if (lb + 1 <= N) {
    D[lb + 1] = query(lb, lb + 1);
    A[lb + 1] = A[lb] + D[lb + 1];
    filled[A[lb + 1]] = 1;
  }

  if (lb - 1 >= 1) {
    D[lb - 1] = query(lb - 1, lb);
    A[lb - 1] = A[lb] + D[lb - 1];
    filled[A[lb - 1]] = 1;
  }

  int L = lb - 2, R = lb + 2;

  while (L >= 1 || R <= N) {
    if (L >= 1) {
      if (D[L] == -1) D[L] = query(L, L + 1);
    }
    if (R <= N) {
      if (D[R] == -1) D[R] = query(R - 1, R);
    }
    if (L >= 1) {
      if (A[L + 1] + D[L] > N || filled[A[L + 1] + D[L]]) {
        A[L] = A[L + 1] - D[L];
      } else if (A[L + 1] - D[L] < 1 || filled[A[L + 1] - D[L]]) {
        A[L] = A[L + 1] + D[L];
      } else {
        int tie_break = query(L, L + 2);
        A[L] = A[L + 1];
        if (tie_break == D[L] + D[L + 1]) {
          A[L] += (A[L + 1] < A[L + 2]) ? -D[L] : D[L];
        } else {
          A[L] += (A[L + 1] < A[L + 2]) ? D[L] : -D[L];
        }
      }

      dbg(A[L]);
      filled[A[L]] = 1;
      L--;
    } else {
      if (A[R - 1] + D[R] > N || filled[A[R - 1] + D[R]]) {
        A[R] = A[R - 1] - D[R];
      } else if (A[R - 1] - D[R] < 1 || filled[A[R - 1] - D[R]]) {
        A[R] = A[R - 1] + D[R];
      } else {
        int tie_break = query(R - 2, R);
        A[R] = A[R - 1];
        if (tie_break == D[L] + D[L + 1]) {
          A[R] += (A[R - 2] < A[R - 1]) ? D[R] : -D[R];
        } else {
          A[R] += (A[R - 2] < A[R - 1]) ? -D[R] : D[R];
        }
      }
      dbg(A[R]);
      filled[A[R]] = 1;
      R++;
    }
  }

  for (int i = 1; i <= N; i++) answer(i, A[i]);
}

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