QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#383193#5414. Stop, Yesterday Please No MoreshepherdAC ✓593ms413984kbC++208.5kb2024-04-09 03:33:502024-04-09 03:33:50

Judging History

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

  • [2024-04-09 03:33:50]
  • 评测
  • 测评结果:AC
  • 用时:593ms
  • 内存:413984kb
  • [2024-04-09 03:33:50]
  • 提交

answer

#include <bits/stdc++.h>

#include <vector>

#pragma GCC optimize("O3,unroll-loops")

#ifdef LLOCAL
#include "debug.h"
#else
#define var(...)
#define debugArr(...)
#endif

using namespace std;

#define len(a) static_cast<int>((a).size())
#define present(c, x) (c.find(x) != c.end())
#define printDecimal(d) std::cout << std::setprecision(d) << std::fixed

using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr const int iinf = 1e9 + 7;
constexpr const ll inf = 1e18;
constexpr const ll mod = 1'000'000'007;

template <typename Fun>
class y_combinator_result {
  Fun fun_;

 public:
  template <typename T>
  explicit y_combinator_result(T&& fun) : fun_(std::forward<T>(fun)) {}

  template <typename... Args>
  decltype(auto) operator()(Args&&... args) {
    return fun_(std::ref(*this), std::forward<Args>(args)...);
  }
};
template <typename Fun>
decltype(auto) y_combinator(Fun&& fun) {
  return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

pair<vector<vector<int>>, int> construct_grid(int n, int m, const string& s) {
  vector<vector<int>> grid_2d(n, vector<int>(m));
  int u = 0, l = 0, r = m - 1, d = n - 1;
  int bu = 0, bl = 0, br = m - 1, bd = n - 1;
  for (auto c : s) {
    switch (c) {
      case 'U': {
        if (bu == u) {
          bu++;
        }
        u++, d++;
        break;
      }
      case 'L': {
        if (bl == l) {
          bl++;
        }
        l++, r++;
        break;
      }
      case 'R': {
        if (br == r) {
          br--;
        }
        r--, l--;
        break;
      }
      case 'D': {
        if (bd == d) {
          bd--;
        }
        d--, u--;
        break;
      }
      default: {
        assert(false);
      }
    }
  }
  int oob = n * m;
  if (bu <= bd && bl <= br) {
    for (int i = bu; i <= bd; i++) {
      for (int j = bl; j <= br; j++) {
        grid_2d[i][j] = 1;
        oob--;
      }
    }
  }
  return make_pair(grid_2d, oob);
}

vector<double> flatten_and_cast(const vector<vector<int>>& grid) {
  vector<double> ret;
  for (const auto& elem : grid) {
    for (auto& x : elem) {
      ret.push_back(x);
    }
  }
  return ret;
}

struct motif_data {
  vector<vector<int>> motif;
  int px, py, mn, mm;
};

motif_data construct_motif(int n, int m, const string& s) {
  int px = 0, py = 0, cx = 0, cy = 0;
  for (auto c : s) {
    switch (c) {
      case 'D': {
        if (cx == 0)
          px++;
        else
          cx--;
        break;
      }
      case 'U': {
        cx++;
        break;
      }
      case 'R': {
        if (cy == 0)
          py++;
        else
          cy--;
        break;
      }
      case 'L': {
        cy++;
        break;
      }
    }
  }
  vector<vector<int>> motif(px + 1, vector<int>(py + 1));
  cx = px, cy = py;
  motif[cx][cy] = 1;
  int num_col = py + 1;
  for (auto c : s) {
    switch (c) {
      case 'D': {
        cx--;
        assert(cx >= 0);
        break;
      }
      case 'U': {
        cx++;
        break;
      }
      case 'L': {
        cy++;
        break;
      }
      case 'R': {
        cy--;
        assert(cy >= 0);
        break;
      }
      default: {
        assert(false);
      }
    }
    while (len(motif) <= cx) motif.emplace_back();
    while (len(motif[cx]) <= cy) motif[cx].push_back(0);
    motif[cx][cy] = 1;
    num_col = max(num_col, cy + 1);
  }
  for (int i = 0; i < len(motif); i++) {
    while (len(motif[i]) < num_col) motif[i].push_back(0);
  }
  return motif_data{motif, px, py, len(motif), num_col};
}

vector<vector<int>> pad_grid(const vector<vector<int>>& grid, int pt, int pb,
                             int pl, int pr) {
  vector<vector<int>> ret;
  for (int i = 0; i < pt; i++) {
    ret.emplace_back();
    for (int j = 0; j < pl; j++) {
      ret.back().push_back(0);
    }
    for (int j = 0; j < len(grid[0]); j++) {
      ret.back().push_back(0);
    }
    for (int j = 0; j < pr; j++) {
      ret.back().push_back(0);
    }
  }
  for (int i = 0; i < len(grid); i++) {
    ret.emplace_back();
    for (int j = 0; j < pl; j++) {
      ret.back().push_back(0);
    }
    for (int j = 0; j < len(grid[i]); j++) {
      ret.back().push_back(grid[i][j]);
    }
    for (int j = 0; j < pr; j++) {
      ret.back().push_back(0);
    }
  }
  for (int i = 0; i < pb; i++) {
    ret.emplace_back();
    for (int j = 0; j < pl; j++) {
      ret.back().push_back(0);
    }
    for (int j = 0; j < len(grid[0]); j++) {
      ret.back().push_back(0);
    }
    for (int j = 0; j < pr; j++) {
      ret.back().push_back(0);
    }
  }
  return ret;
}

namespace kactl {
typedef vector<ll> vl;
typedef complex<double> C;
void fft(vector<C>& a) {
  int n = len(a), L = 31 - __builtin_clz(n);
  static vector<complex<long double>> R(2, 1);
  static vector<C> rt(2, 1);  // (^ 10% faster if double)
  for (static int k = 2; k < n; k *= 2) {
    R.resize(n);
    rt.resize(n);
    auto x = polar(1.0L, acos(-1.0L) / k);
    for (int i = k; i < 2 * k; i++)
      rt[i] = R[i] = i & 1 ? R[i / 2] * x : R[i / 2];
  }
  vector<int> rev(n);
  for (int i = 0; i < n; i++) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
  for (int i = 0; i < n; i++)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int k = 1; k < n; k *= 2)
    for (int i = 0; i < n; i += 2 * k)
      for (int j = 0; j < k; j++) {
        // C z = rt[j+k] * a[i+j+k]; // (25% faster if hand-rolled)  ///
        // include-line
        auto x = (double*)&rt[j + k],
             y = (double*)&a[i + j + k];  /// exclude-line
        C z(x[0] * y[0] - x[1] * y[1],
            x[0] * y[1] + x[1] * y[0]);  /// exclude-line
        a[i + j + k] = a[i + j] - z;
        a[i + j] += z;
      }
}
vector<double> conv(const vector<double>& a, const vector<double>& b) {
  if (a.empty() || b.empty()) return {};
  vector<double> res(len(a) + len(b) - 1);
  int L = 32 - __builtin_clz(len(res)), n = 1 << L;
  vector<C> in(n), out(n);
  copy(begin(a), end(a), begin(in));
  for (int i = 0; i < len(b); i++) in[i].imag(b[i]);
  fft(in);
  for (C& x : in) x *= x;
  for (int i = 0; i < n; i++) out[i] = in[-i & (n - 1)] - conj(in[i]);
  fft(out);
  for (int i = 0; i < len(res); i++) res[i] = imag(out[i]) / (4 * n);
  return res;
}
// template <int M>
// vl convMod(const vl& a, const vl& b) {
//   if (a.empty() || b.empty()) return {};
//   vl res(len(a) + len(b) - 1);
//   int B = 32 - __builtin_clz(len(res)), n = 1 << B, cut = int(sqrt(M));
//   vector<C> L(n), R(n), outs(n), outl(n);
//   for (int i = 0; i < len(a); i++) L[i] = C((int)a[i] / cut, (int)a[i] %
//   cut); for (int i = 0; i < len(b); i++) R[i] = C((int)b[i] / cut, (int)b[i]
//   % cut); fft(L), fft(R); for (int i = 0; i < n; i++) {
//     int j = -i & (n - 1);
//     outl[j] = (L[i] + conj(L[j])) * R[i] / (2.0 * n);
//     outs[j] = (L[i] - conj(L[j])) * R[i] / (2.0 * n) / 1i;
//   }
//   fft(outl), fft(outs);
//   for (int i = 0; i < len(res); i++) {
//     ll av = ll(real(outl[i]) + .5), cv = ll(imag(outs[i]) + .5);
//     ll bv = ll(imag(outl[i]) + .5) + ll(real(outs[i]) + .5);
//     res[i] = ((av % M * cut + bv) % M * cut + cv) % M;
//   }
//   return res;
// }
}  // namespace kactl

int main() {
  std::ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, m, k;
    cin >> n >> m >> k;
    string s;
    cin >> s;
    auto [grid, oob] = construct_grid(n, m, s);
    auto [motif, px, py, mn, mm] = construct_motif(n, m, s);
    int pad_bottom = 0, pad_right = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        pad_bottom = max(pad_bottom, i + mn - px - 1 - len(grid) + 1);
        pad_right = max(pad_right, j + mm - py - 1 - len(grid[0]) + 1);
      }
    }
    grid = pad_grid(grid, px, pad_bottom, py, pad_right);
    int target = n * m - oob - k;
    if (target < 0) {
      cout << 0 << '\n';
      continue;
    }
    n = len(grid), m = len(grid[0]);
    for (int i = 0; i < len(motif) - 1; i++) {
      while (len(motif[i]) < m) motif[i].push_back(0);
    }
    auto grid_1d = flatten_and_cast(grid);
    auto motif_1d = flatten_and_cast(motif);
    reverse(motif_1d.begin(), motif_1d.end());
    auto d = kactl::conv(grid_1d, motif_1d);
    int ret = 0;
    for (int i = 0; i + mn <= n; i++) {
      for (int j = 0; j + mm <= m; j++) {
        if (fabs(d[i * m + j + len(motif_1d) - 1] - target) <= 1e-8) {
          ret++;
        }
      }
    }
    cout << ret << '\n';
  }
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3912kb

input:

3
4 5 3
ULDDRR
4 5 0
UUUUUUU
4 5 10
UUUUUUU

output:

2
20
0

result:

ok 3 number(s): "2 20 0"

Test #2:

score: 0
Accepted
time: 60ms
memory: 10620kb

input:

1060
19 12 0
UDLDDUUUUDDDLLRDUDUURULUUUDRDUDRDRLRLRLULULLLDLDDRLUUUURUUUDDRLLRUUUDULURUULLRDRLRDDURDUUURRRLURLRUULRRUDURDLUUURDLURDDLUUURDDRLLURRDLRUDLRDRLLRRDRDDLDRURRRLUDULLLRUUDLRRURRDLLRRRDLLRDDDLRLRURURDDDL
11 1 0
UR
3 18 33
UDRLR
17 11 132
RLDRDLDRUU
6 10 13
UULUDDLRDLUUDLDD
1 15 0
D
6 20 50
D...

output:

228
11
20
99
18
15
34
240
15
0
0
13
14
18
26
16
1
19
108
8
2
2
3
7
0
30
16
21
0
8
10
9
15
5
320
11
7
3
0
0
12
0
11
0
0
14
0
22
36
51
23
7
6
4
2
48
28
8
63
22
49
13
10
4
108
10
18
44
0
15
9
0
4
30
14
99
105
10
14
17
0
66
10
11
28
52
34
56
33
14
56
90
14
0
121
3
48
30
36
13
0
30
7
8
3
11
16
45
20
34
0...

result:

ok 1060 numbers

Test #3:

score: 0
Accepted
time: 155ms
memory: 113744kb

input:

1
1000 1000 979065
DDUULULUDULLULLDLUULURRLDURLRDLRRUURUUUDLRLUUDUUDUDLLDDDULU

output:

958416

result:

ok 1 number(s): "958416"

Test #4:

score: 0
Accepted
time: 341ms
memory: 205020kb

input:

1
1000 1000 943471
LRLDLURLDLRDRDUULULRDDLLRURDUURLLDDLDLDDLLLUUURLDRUDRLLUUUUUDLUUDLURURRDLRLRRRLULRRULURLRRDLDRLUDRRLDDLUDRRLLUDLLLRDULRRRRLDUUDRDLULUUUUDRRDULUDLLUUDLDURDRRLRRLDRLDDRURURLUULRRLDLLRLRDRRUULDLDLULLDLLRULLRUULURDURRLUUDUULLULDLRUDDLRLRLLUDDDLLLUDRRLDDULRRURRDURDDRDLLULRLULURLRDLLURD...

output:

889224

result:

ok 1 number(s): "889224"

Test #5:

score: 0
Accepted
time: 593ms
memory: 413984kb

input:

1
1000 1000 315808
LLRURURRDDDULLDDUDRDLRLLLDDDLUDRDURLDULRLRULUUDLUULUUDULLLLDDURLDUULUUDLLDLLDRUDUULRLLRLRUURLRLULLDDLLDUDLLRUUDRLDLUULDLLDRRRURDULLDRRRDURURDRLDURURUDLURLDURRLRRUDUDURDRLRRRDLRRURLURUDRRLDLRULLDLUURDURLURLLRDLRDRUURURDRUDUUUDLRRLUDLUUDUDDRRDUULUUDDRLLULDUUDRURRDRLULRLULDURLURUDLLD...

output:

426

result:

ok 1 number(s): "426"

Test #6:

score: 0
Accepted
time: 190ms
memory: 113476kb

input:

1
1000 1000 986018
LLULDRRRDDURRUDRUURRRDDLUUDUULRULRDULLD

output:

972180

result:

ok 1 number(s): "972180"

Test #7:

score: 0
Accepted
time: 437ms
memory: 206232kb

input:

1
1000 1000 945431
DDRRURUUDLDULLDLDDLRULDLLDDRRLUDRLUURRLDRDLURUURRRRLRURLURULLLDRDDDRRRLDLDRLRDDUURRURDDDLRUURLUURLRDUDDDLLDUURLDLUDLLRRDUUDRLUULLUULDLURRUDLUURLRLRURDUDRRRDRLRUDLLLLURLULRLRLRRDDUDLRLDUUUULUDLLURRLURRDLRURRRULDDLLLRLRDLUDLLDDRULDUULRDDUUDDUDLURDULLDUDDLULRULDRLDDULDULLUDLULUDRURRR...

output:

893000

result:

ok 1 number(s): "893000"

Test #8:

score: 0
Accepted
time: 445ms
memory: 227968kb

input:

1
1000 1000 460035
RDDUURDULDDLDDLDDLDRRULLRLUURLURRRDRUDDDRDLDLDULUDLRLLRRLRRURRRDLRLUDRDURULDRRDDDDDDLRLDULUULDUDRLLUUUURUUDRURLRRULDRDRUUUUULULRURDDRLRULLLRDRRULUDDUDDLLLRDRUULUUDDRLURDLDURRDLRRLDRRUDLUULRDLURULLDLRLLDDURDUDLDULDLLRULRDLRLUULLUDRUDDDLRRDULULLRUURLUURRLLLLRLDRURLLRLDRRDDDRLUUUUDUL...

output:

417

result:

ok 1 number(s): "417"

Test #9:

score: 0
Accepted
time: 186ms
memory: 113312kb

input:

1
1000 1000 992010
LLLLLDLDRRLUDRR

output:

1999

result:

ok 1 number(s): "1999"

Test #10:

score: 0
Accepted
time: 373ms
memory: 205476kb

input:

1
1000 1000 919600
LLDLRUDRLURRUDRDRRDLRUDLRRRUUULDLDURDDDRUURRRLLURULDRLRLULLULDRULULRLRRRURLDDDRUUULUDLLLLRRLLRDDRDULUDLRLRLDRLUDUDURRULUULLDULUULDLLDRDULUDLDULDDUULDDRRURDRDULRRLDRRDUURURRLUUUDRRLDRRDDLULRDDLDLLRLRLLLRULUUUURRRLDLRUDRRLRURDRLDULLLUDRULLDLDRRUUDLRRLLRLDDLUDLRLRRURUUDUULUDURDURRLUU...

output:

944

result:

ok 1 number(s): "944"

Test #11:

score: 0
Accepted
time: 470ms
memory: 209948kb

input:

1
1000 1000 804351
DLRLDLLLLUDRDURRLDDRRLRUULURURDDDRDLRUDDULRRLLULURDRUUDRURRLURRRDRURRDRLULRDLRRDRRDDUDLUDLDULRUURRLRUUDRLDDRDDUUDULUULUUUDLRURULLRDUUDDDRRLDRUDDUUDRURLRDRUDLRLDDRRLLRLRDUDDULLULRLLDDUDDDUULDULLRRULULDUUULUDRRDRLUDLRRDDUDLRRDDLDLDRUULRRRRRLRLULLRDDRDDDULDRRURUDDLURLRLURLRDRULUDULUU...

output:

640000

result:

ok 1 number(s): "640000"