Submission #152814

#	Time	Username	Problem	Language	Result	Execution time	Memory
152814		doowey	Xylophone (JOI18_xylophone)	C++14	100 / 100	134 ms	508 KiB

xylophone

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

using namespace std;

typedef long long ll;

const int N = 5005;
int to[N];
int thr[N];
int sign[N];
int bal[N];

void solve(int n) {
  for(int i = 1; i <= n - 1; i ++ ){
    to[i] = query(i, i + 1);
  }
  for(int i = 1; i <= n - 2; i ++ ){
    thr[i] = query(i, i + 2);
  }
  sign[2] = 1;
  for(int i = 3; i <= n; i ++ ){
    if(to[i - 2] + to[i - 1] != thr[i - 2]){
      sign[i] = 1 - sign[i - 1];
    }
    else{
      sign[i] = sign[i - 1];
    }
  }
  int sg;
  for(int i = 2; i <= n; i ++ ){
    if(sign[i] == 1) sg = +1;
    else sg = -1;
    bal[i] = bal[i - 1] + sg * to[i - 1];
  }
  int low = 1;
  int high = 1;
  for(int i = 2; i <= n; i ++ ){
    if(bal[i] < bal[low])
      low = i;
    if(bal[i] > bal[high])
      high = i;
  }
  if(low > high){
    for(int i = 2 ; i <= n; i ++ ){
      sign[i] = 1 - sign[i];
    }
  }
  low = 0;
  for(int i = 2; i <= n; i ++ ){
    if(sign[i] == 1) sg = +1;
    else sg = -1;
    bal[i] = bal[i - 1] + sg * to[i - 1];
    low = min(low, bal[i]);
  }
  for(int i = 1; i <= n; i ++ ){
    answer(i, bal[i] - low + 1);
  }
}

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