Submission #64900

#	Time	Username	Problem	Language	Result	Execution time	Memory
64900		funcsr	Xylophone (JOI18_xylophone)	C++17	100 / 100	197 ms	20892 KiB

xylophone

#include "xylophone.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int N;
int A[5000];
bool used[5000];
int cache[5000][5000];
bool ok(int x) {
  return x>=0 && x<N && !used[x];
}
void setA(int pos, int val) {
  assert(ok(val));
  used[val] = true;
  A[pos] = val;
}

int ask(int l, int r) {
  if (l > r) swap(l, r);
  if (l == r) return 0;
  if (cache[l][r]) return cache[l][r];
  return cache[l][r] = query(l+1, r+1);
}
int f(int a, int b, int d, int m) {
  if (a < b) {
    if (b+d-a == m) return b+d;
    else return b-d;
  }
  else {
    if (a-(b-d) == m) return b-d;
    else return b+d;
  }
}

void solve(int NN) {
  N = NN;
  int lo = 0, hi = N-1;
  while (hi-lo > 1) {
    int mid = (lo+hi)/2;
    if (ask(0, mid) == N-1) hi = mid;
    else lo = mid;
  }
  rep(i, N) A[i] = -1;
  setA(hi, N-1);
  setA(hi-1, N-1-ask(hi-1, hi));

  for (int i=hi+1; i<N; i++) {
    //cout<<A[i-2]<<","<<A[i-1]<<",?\n";
    int d = ask(i-1, i);
    vector<int> qs;
    if (ok(A[i-1]+d)) qs.pb(A[i-1]+d);
    if (ok(A[i-1]-d)) qs.pb(A[i-1]-d);
    if (qs.size()==2) {
      qs.clear();
      qs.pb(f(A[i-2], A[i-1], d, ask(i-2, i)));
    }
    assert(qs.size() == 1);
    setA(i, qs[0]);
  }
  for (int i=hi-2; i>=0; i--) {
    //cout<<"?,"<<A[i+1]<<","<<A[i+2]<<"\n";
    int d = ask(i, i+1);
    vector<int> qs;
    if (ok(A[i+1]+d)) qs.pb(A[i+1]+d);
    if (ok(A[i+1]-d)) qs.pb(A[i+1]-d);
    if (qs.size()==2) {
      qs.clear();
      qs.pb(f(A[i+2], A[i+1], d, ask(i, i+2)));
    }
    assert(qs.size() == 1);
    setA(i, qs[0]);
  }
  //rep(i, N) cout << A[i]<<",";cout<<"\n";
  rep(i, N) answer(i+1, A[i]+1);
}

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