Submission #278121

#	Time	Username	Problem	Language	Result	Execution time	Memory
278121		erray	Xylophone (JOI18_xylophone)	C++17	100 / 100	163 ms	504 KiB

xylophone

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

using namespace std;

template<typename T, typename F> string to_string(pair<T, F> p);
string to_string(string s) {
  return '"' + s + '"';
}
string to_string(char c) {
  return (string) "'" + c + "'";
}
string to_string(const char* p) {
  return to_string((string) p);
}
string to_string(bool B) {
  return (B ? "true" : "false");
}
string to_string(vector<bool> v) {
  string res = "{";
  for (int i = 0; i < (int) v.size(); ++i) {
    if ((int) res.size() > 1) res += ", ";
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template<size_t T> string to_string(bitset<T> bs) {
  return bs.to_string();
}
template<typename T> string to_string(T v) {
  string res = "{";
  for (auto& el : v) {
    if ((int) res.size() > 1) res += ", ";
    res += to_string(el);
  }
  res += "}";
  return res;
}
template<typename T, typename F> string to_string(pair<T, F> p) {
  return '(' + to_string(p.first) + ", " + to_string(p.second) + ')';
}
void debug_out() {
  cerr << endl;
}
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:" , debug_out(__VA_ARGS__)
#else
#define debug(...) (void) 37
#endif

//int query(int s, int e);

//int answer(int ind, int v); 

void solve(int n) {
  vector<int> f(n);
  f[1] = query(1, 2);
  for (int i = 2; i < n; ++i) {
    int th = query(i - 1, i + 1), tw = query(i, i + 1);
    debug(th, tw);
    if (th == abs(f[i - 1])) {
      f[i] = -tw;
    } else if (th > abs(f[i - 1])) {
      if (tw >= th) {
        f[i] = -tw;          
      } else {
        f[i] = tw;          
      }       
    }      
  }
  bool cur = false;
  for (int i = 0; i < n; ++i) {
    if (f[i] < 0) cur ^= 1;
    f[i] = abs(f[i]) * (cur ? 1 : -1);
  }
  debug(f);
  vector<int> pref(1, 0);
  for (int i = 1; i < n; ++i) pref.push_back(pref.back() + f[i]);
  int mn_ind = (int) (min_element(pref.begin(), pref.end()) - pref.begin()), mx_ind = (int) (max_element(pref.begin(), pref.end()) - pref.begin());
  if (mx_ind < mn_ind) {
    swap(mx_ind, mn_ind);
    for (auto& el : f) el = -el;
  }
  vector<int> ans(n);
  ans[mn_ind] = 1;
  for (int i = mn_ind + 1; i < n; ++i) {
    ans[i] = ans[i - 1] + f[i];
  }
  for (int i = mn_ind - 1; i >= 0; --i) {
    ans[i] = ans[i + 1] - f[i + 1];
  }
  debug(ans);
  for (int i = 0; i < n; ++i) {
    answer(i + 1, ans[i]);  
  }
}                                                                          

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