QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#282544	#6851. Cyclically Isomorphic	zlxFTH	AC ✓	101ms	9212kb	C++17	1.6kb	2023-12-12 12:51:48	2023-12-12 12:51:48

Judging History

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

[2023-12-12 12:51:48]
评测

测评结果：AC
用时：101ms
内存：9212kb

查看

[2023-12-12 12:51:48]
提交

answer

#include <bits/stdc++.h>
using namespace std;

using ULL = unsigned long long;
const ULL base = 19260817;

void solve() {
  int n, m;
  cin >> n >> m;
  vector<string> s(n), t(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    t[i] = s[i] + s[i];
  }
  vector<vector<ULL>> h(n, vector<ULL>(m * 2));
  for (int i = 0; i < n; i++) {
    auto &cur = t[i];
    h[i][0] = cur[0] - 'a' + 1;
    for (int j = 0; j + 1 < m * 2; j++) {
      h[i][j + 1] = h[i][j] * base + cur[j + 1] - 'a' + 1;
    }
  }
  vector<ULL> p(m * 2 + 1);
  p[0] = 1;
  for (int i = 1; i < m * 2 + 1; i++) {
    p[i] = p[i - 1] * base;
  }
  auto calc = [&](int id, int l, int r) {
    auto &cur = t[id];
    ULL res = h[id][r];
    if (l) res -= h[id][l - 1] * p[r - l + 1];
    return res;
  };
  auto qry = [&](int i, int j) {
    ULL tar = calc(j, 0, m - 1);
    for (int k = 0; k < m; k++) {
      if (calc(i, k, k + m - 1) == tar) return 1;
    }
    return 0;
  };
  if (n <= 1000) {
    vector<vector<int>> ans(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
      for (int j = i; j < n; j++) {
        ans[i][j] = ans[j][i] = qry(i, j);
      }
    }
    int q;
    cin >> q;
    while (q--) {
      int x, y;
      cin >> x >> y;
      x--, y--;
      cout << (ans[x][y] ? "Yes\n" : "No\n");
    }
  } else {
    int q;
    cin >> q;
    while (q--) {
      int x, y;
      cin >> x >> y;
      x--, y--;
      cout << (qry(x, y) ? "Yes\n" : "No\n");
    }
  }
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 101ms

memory: 9212kb

input:

5
10 10000
afcadffafeeebdfedfdafecfdbeecbcadfedcffaedecbacffedeccacfcbfbbdbcefbdefefebcbeacfbaafddbabcbfaeddaaefebbddafaaaaaedcbbdaafaffcbeeebfbbeedebabfbdbaceabfcccfedbdeafccbaffdeadbefbfeadbbedeeabbaafebaceeaeedbaddfecdefaabdbcfadadaebbdeedcfeeabbbdbcefdadbeecafcabbddddbcacadbbcddeddbbeecbdadefbaa...

output:

No
No
No
Yes
Yes
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
No
No
No
No
No
No
No
No
Yes
No
Yes
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
Yes
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
Yes
No
Yes
No
Yes
No
No
No
No
No
No
No
No
Yes
Yes
Ye...

result:

ok 500000 lines