QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104131#6400. Game: Celestehos_lyricWA 236ms3820kbC++147.5kb2023-05-09 01:42:172023-05-09 01:42:58

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-09 01:42:58]
  • 评测
  • 测评结果:WA
  • 用时:236ms
  • 内存:3820kb
  • [2023-05-09 01:42:17]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }

////////////////////////////////////////////////////////////////////////////////
// 2^61 - 1 = 2'305'843'009'213'693'951
struct ModLong61 {
  static constexpr unsigned long long M = (1ULL << 61) - 1;
  unsigned long long x;
  ModLong61() : x(0ULL) {}
  ModLong61(unsigned x_) : x(x_ % M) {}
  ModLong61(unsigned long long x_) : x(x_ % M) {}
  ModLong61(int x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModLong61(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModLong61 &operator+=(const ModLong61 &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModLong61 &operator-=(const ModLong61 &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModLong61 &operator*=(const ModLong61 &a) {
    const unsigned __int128 y = static_cast<unsigned __int128>(x) * a.x;
    x = (y >> 61) + (y & M);
    x = (x >= M) ? (x - M) : x;
    return *this;
  }
  ModLong61 &operator/=(const ModLong61 &a) { return (*this *= a.inv()); }
  ModLong61 pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModLong61 a = *this, b = 1ULL; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModLong61 inv() const {
    unsigned long long a = M, b = x; long long y = 0, z = 1;
    for (; b; ) { const unsigned long long q = a / b; const unsigned long long c = a - q * b; a = b; b = c; const long long w = y - static_cast<long long>(q) * z; y = z; z = w; }
    assert(a == 1ULL); return ModLong61(y);
  }
  ModLong61 operator+() const { return *this; }
  ModLong61 operator-() const { ModLong61 a; a.x = x ? (M - x) : 0ULL; return a; }
  ModLong61 operator+(const ModLong61 &a) const { return (ModLong61(*this) += a); }
  ModLong61 operator-(const ModLong61 &a) const { return (ModLong61(*this) -= a); }
  ModLong61 operator*(const ModLong61 &a) const { return (ModLong61(*this) *= a); }
  ModLong61 operator/(const ModLong61 &a) const { return (ModLong61(*this) /= a); }
  template <class T> friend ModLong61 operator+(T a, const ModLong61 &b) { return (ModLong61(a) += b); }
  template <class T> friend ModLong61 operator-(T a, const ModLong61 &b) { return (ModLong61(a) -= b); }
  template <class T> friend ModLong61 operator*(T a, const ModLong61 &b) { return (ModLong61(a) *= b); }
  template <class T> friend ModLong61 operator/(T a, const ModLong61 &b) { return (ModLong61(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModLong61 &a) const { return (x == a.x); }
  bool operator!=(const ModLong61 &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModLong61 &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////

#include <chrono>
#include <random>
// [l, r]
Int randLong(Int l, Int r) {
  static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  return uniform_int_distribution<Int>(l, r)(rng);
}
const ModLong61 BASE = randLong(0, ModLong61::M - 1);

////////////////////////////////////////////////////////////////////////////////


int N;
Int L, R;
vector<Int> X;
vector<int> A;

int E;
vector<ModLong61> BB;

struct Node {
  int l, r;
  ModLong61 h;
};
int nodesLen;
vector<Node> nodes;
int newLeaf(ModLong61 h) {
  const int u = nodesLen++;
  nodes[u].l = -1;
  nodes[u].r = -1;
  nodes[u].h = h;
  return u;
}
int newInternal(int e, int l, int r) {
  const int u = nodesLen++;
  nodes[u].l = l;
  nodes[u].r = r;
  nodes[u].h = nodes[l].h + BB[e - 1] * nodes[r].h;
  return u;
}

int cmp(int u, int v) {
  for (int e = E; --e >= 0; ) {
    if (nodes[nodes[u].r].h != nodes[nodes[v].r].h) {
      u = nodes[u].r;
      v = nodes[v].r;
    } else {
      u = nodes[u].l;
      v = nodes[v].l;
    }
  }
  return (nodes[u].h.x > nodes[v].h.x) ? +1 : (nodes[u].h.x < nodes[v].h.x) ? -1 : 0;
}

int incr(int e, int u, int pos) {
  if (e == 0) {
    return newLeaf(nodes[u].h + 1);
  } else {
    if (pos >> (e - 1) & 1) {
      return newInternal(e, nodes[u].l, incr(e - 1, nodes[u].r, pos));
    } else {
      return newInternal(e, incr(e - 1, nodes[u].l, pos), nodes[u].r);
    }
  }
}
int incr(int u, int pos) {
  return incr(E, u, pos);
}

void dfs(int e, int a, int u, vector<int> &as) {
  if (!nodes[u].h) return;
  if (e == 0) {
    for (int i = 0; i < (int)nodes[u].h.x; ++i) {
      as.push_back(a);
    }
  } else {
    dfs(e - 1, a | 1 << (e - 1), nodes[u].r, as);
    dfs(e - 1, a               , nodes[u].l, as);
  }
}
void dfs(int u, vector<int> &as) {
  dfs(E, 0, u, as);
}

int main() {
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%d%lld%lld", &N, &L, &R);
    X.resize(N);
    for (int i = 0; i < N; ++i) {
      scanf("%lld", &X[i]);
    }
    A.resize(N);
    for (int i = 0; i < N; ++i) {
      scanf("%d", &A[i]);
    }
    
    for (E = 0; !(N < 1 << E); ++E) {}
    BB.resize(E + 1);
    BB[0] = 1;
    for (int e = 1; e <= E; ++e) {
      BB[e] = BB[e - 1] * BASE;
    }
    
    nodesLen = 1 << (E + 1);
    nodes.resize((1 << (E + 1)) + (E + 1) * N);
    for (int u = 1; u < 1 << E; ++u) {
      nodes[u].l = u << 1;
      nodes[u].r = u << 1 | 1;
      nodes[u].h = 0;
    }
    for (int u = 1 << E; u < 1 << (E + 1); ++u) {
      nodes[u].l = -1;
      nodes[u].r = -1;
      nodes[u].h = 0;
    }
    
    vector<int> dp(N, -1);
    dp[0] = incr(1, A[0]);
    vector<int> que(N);
    int qb = 0, qe = 0;
    for (int i = 1, j = 0; i < N; ++i) {
      for (; X[i] - X[j] >= L; ++j) {
        if (~dp[j]) {
          // push
          for (; qe - qb >= 1 && cmp(dp[que[qe - 1]], dp[j]) <= 0; --qe) {}
          que[qe++] = j;
        }
      }
      // pop
      for (; qe - qb >= 1 && X[i] - X[que[qb]] > R; ++qb) {}
      if (qe - qb >= 1) {
        dp[i] = incr(dp[que[qb]], A[i]);
      }
    }
    
    if (~dp[N - 1]) {
      vector<int> ans;
      dfs(dp[N - 1], ans);
      printf("%d\n", (int)ans.size());
      for (int h = 0; h < (int)ans.size(); ++h) {
        if (h) printf(" ");
        printf("%d", ans[h]);
      }
      puts("");
    } else {
      puts("-1");
    }
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3744kb

input:

2
5 2 3
1 2 3 4 5
5 2 3 1 4
3 1 2
1 4 7
3 3 3

output:

3
5 4 3
-1

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 236ms
memory: 3820kb

input:

10000
57 8 11
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
11 16 7 7 10 13 9 14 10 1 12 4 8 13 3 20 16 7 16 19 20 8 19 7 16 6 17 13 7 19 17 11 12 17 6 3 7 8 14 2 4 15 5 18 16 7 20 9 1...

output:

7
20 20 19 14 12 11 3
-1
6
6 5 3 2 1 1
-1
185
20 20 20 20 20 20 20 20 19 19 19 19 19 19 19 19 19 19 19 19 18 18 18 18 18 17 17 17 17 17 17 17 17 16 16 16 16 16 16 16 16 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 14 14 14 14 14 14 14 13 13 13 13 13 13 13 13 13 12 12 12 12 12 12 12 12...

result:

wrong answer 12th lines differ - expected: '139', found: '140'