Submission #212291

#	Time	Username	Problem	Language	Result	Execution time	Memory
212291		tselmegkh	Xylophone (JOI18_xylophone)	C++14	0 / 100	5 ms	256 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());

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 = 2, 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;
  for(int i = t + 1; i <= n; i++){
    int res = n - query(t, i);
    if(res == ans[i - 1]){
      res = ans[i - 1] + query(i - 1, i);
    }
    ans[i] = res;
  }
  for(int i = s - 1; i >= 1; i--){
    int res = 1 + query(i, s);
    if(res == ans[i + 1]){
      res = ans[i + 1] - query(i, i + 1);
    }
    ans[i] = res;
  }
  for(int i = s + 1; i < t; i++){
    int res = 1 + query(s, i);
    if(res == ans[i - 1]){
      res = ans[i - 1] - query(i - 1, i);
    }
    ans[i] = res;
  }
  for(int i = 1; i <= n; i++){
    answer(i, ans[i]);
  }
}

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