Submission #212335

#	Time	Username	Problem	Language	Result	Execution time	Memory
212335		tselmegkh	Xylophone (JOI18_xylophone)	C++14	0 / 100	5 ms	384 KiB

xylophone

#include<bits/stdc++.h>
#include "xylophone.h"
using namespace std;
const int N = 1e5 + 5, inf = 1e9;

#define pb push_back
#define mp make_pair
#define ll long long
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*int query(int l, int r){
  cout << l << ' ' << r << endl;
  int res; cin >> res;
  return res;
}
void answer(int i, int x){
  cout << i << " = " << x << '\n';
}*/
void solve(int n){
  vi ans(n + 1);
  int s, t;
  int l = 1, r = n - 1;
  while(l != r){
    int mid = (l + r + 1) / 2;
    if(query(mid, n) < n - 1){
      r = mid - 1;
    }else{
      l = mid;
    }
  }
  s = l;
  l = s + 1, r = n;
  while(l != r){
    int mid = (l + r) / 2;
    if(query(s, mid) < n - 1){
      l = mid + 1;
    }else{
      r = mid;
    }
  }
  t = r;
  ans[s] = 1, ans[t] = n;
  if(t < n)ans[t + 1] = n - query(t, t + 1);
  if(t > 1)ans[s - 1] = 1 + query(s - 1, s);
  for(int i = t + 2; i <= n; i++){
    int res = query(i - 1, i), res2 = query(i - 2, i); 
    if(res2 == abs(ans[i - 1] - ans[i - 2])){
      int x = (ans[i - 1] > ans[i - 2]) ? (-1) : (1);
      ans[i] = ans[i - 1] + x * res;
    }else{
      int x = (ans[i - 1] > ans[i - 2]) ? (1) : (-1);
      ans[i] = ans[i - 1] + x * res;
    }
  }
  for(int i = s - 2; i >= 1; i--){
    int res = query(i, i + 1), res2 = query(i, i + 2);
    if(res2 == abs(ans[i + 1] - ans[i + 2])){
      int x = (ans[i + 1] > ans[i + 2]) ? (-1) : (1);
      ans[i] = ans[i + 1] + x * res;
    }else{
      int x = (ans[i + 1] > ans[i + 2]) ? (1) : (-1);
      ans[i] = ans[i + 1] + x * res;
    }
  }
  if(s < r - 1){
    ans[s + 1] = 1 + query(s, s + 1);
    for(int i = s + 2; i < t; i++){
      int res = query(i - 1, i), res2 = query(i - 2, i);
      if(res2 == abs(ans[i - 1] - ans[i - 2])){
        int x = (ans[i - 1] > ans[i - 2]) ? (-1) : (1);
        ans[i] = ans[i - 1] + x * res;
      }else{
        int x = (ans[i - 1] > ans[i - 2]) ? (1) : (-1);
        ans[i] = ans[i - 1] + x * res;
      }
    }
  }
  for(int i = 1; i <= n; i++){
    answer(i, ans[i]);
  }
}

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