Submission #293655

#	Time	Username	Problem	Language	Result	Execution time	Memory
293655		rama_pang	Xylophone (JOI18_xylophone)	C++14	100 / 100	125 ms	632 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;

void solve(int N) {
  vector<int> dif1;
  vector<int> dif2;
  for (int i = 0; i + 1 < N; i++) {
    dif1.emplace_back(query(i + 1, i + 2));
  }
  for (int i = 0; i + 2 < N; i++) {
    dif2.emplace_back(query(i + 1, i + 3));
  }
  vector<int> ans(N);
  ans[0] = 0;
  ans[1] = dif1[0];
  for (int i = 2; i < N; i++) {
    if (dif1[i - 2] + dif1[i - 1] == dif2[i - 2]) {
      if (ans[i - 2] < ans[i - 1]) {
        ans[i] = ans[i - 1] + dif1[i - 1];
      } else {
        ans[i] = ans[i - 1] - dif1[i - 1];
      }
    } else {
      if (ans[i - 2] < ans[i - 1]) {
        ans[i] = ans[i - 1] - dif1[i - 1];
      } else {
        ans[i] = ans[i - 1] + dif1[i - 1];
      }
    }
  }
  int mn = *min_element(begin(ans), end(ans));
  for (int i = 0; i < N; i++) {
    ans[i] -= mn - 1;
  }
  if (min_element(begin(ans), end(ans)) > max_element(begin(ans), end(ans))) {
    for (int i = 0; i < N; i++) {
      ans[i] = N - ans[i] + 1;
    }
  }
  for (int i = 0; i < N; i++) {
    answer(i + 1, ans[i]);
  }
}

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