QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #870573 | #8618. Have You Seen This Subarray? | ucup-team987# | WA | 0ms | 7756kb | C++20 | 8.4kb | 2025-01-25 16:51:53 | 2025-01-25 16:52:00 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<array>
#include<chrono>
#include<random>
#include<cassert>
using namespace std;
#line 2 "string/rolling-hash.hpp"
#include <string>
#include <vector>
using namespace std;
#line 2 "internal/internal-hash.hpp"
namespace internal {
using i64 = long long;
using u64 = unsigned long long;
using u128 = __uint128_t;
template <int BASE_NUM = 2>
struct Hash : array<u64, BASE_NUM> {
using array<u64, BASE_NUM>::operator[];
static constexpr int n = BASE_NUM;
Hash() : array<u64, BASE_NUM>() {}
static constexpr u64 md = (1ull << 61) - 1;
constexpr static Hash set(const i64 &a) {
Hash res;
fill(begin(res), end(res), cast(a));
return res;
}
Hash &operator+=(const Hash &r) {
for (int i = 0; i < n; i++)
if (((*this)[i] += r[i]) >= md) (*this)[i] -= md;
return *this;
}
Hash &operator+=(const i64 &r) {
u64 s = cast(r);
for (int i = 0; i < n; i++)
if (((*this)[i] += s) >= md) (*this)[i] -= md;
return *this;
}
Hash &operator-=(const Hash &r) {
for (int i = 0; i < n; i++)
if (((*this)[i] += md - r[i]) >= md) (*this)[i] -= md;
return *this;
}
Hash &operator-=(const i64 &r) {
u64 s = cast(r);
for (int i = 0; i < n; i++)
if (((*this)[i] += md - s) >= md) (*this)[i] -= md;
return *this;
}
Hash &operator*=(const Hash &r) {
for (int i = 0; i < n; i++) (*this)[i] = modmul((*this)[i], r[i]);
return *this;
}
Hash &operator*=(const i64 &r) {
u64 s = cast(r);
for (int i = 0; i < n; i++) (*this)[i] = modmul((*this)[i], s);
return *this;
}
Hash operator+(const Hash &r) { return Hash(*this) += r; }
Hash operator+(const i64 &r) { return Hash(*this) += r; }
Hash operator-(const Hash &r) { return Hash(*this) -= r; }
Hash operator-(const i64 &r) { return Hash(*this) -= r; }
Hash operator*(const Hash &r) { return Hash(*this) *= r; }
Hash operator*(const i64 &r) { return Hash(*this) *= r; }
Hash operator-() const {
Hash res;
for (int i = 0; i < n; i++) res[i] = (*this)[i] == 0 ? 0 : md - (*this)[i];
return res;
}
friend Hash pfma(const Hash &a, const Hash &b, const Hash &c) {
Hash res;
for (int i = 0; i < n; i++) res[i] = modfma(a[i], b[i], c[i]);
return res;
}
friend Hash pfma(const Hash &a, const Hash &b, const i64 &c) {
Hash res;
u64 s = cast(c);
for (int i = 0; i < n; i++) res[i] = modfma(a[i], b[i], s);
return res;
}
Hash pow(long long e) {
Hash a{*this}, res{Hash::set(1)};
for (; e; a *= a, e >>= 1) {
if (e & 1) res *= a;
}
return res;
}
static Hash get_basis() {
static auto rand_time =
chrono::duration_cast<chrono::nanoseconds>(
chrono::high_resolution_clock::now().time_since_epoch())
.count();
static mt19937_64 rng(rand_time);
Hash h;
for (int i = 0; i < n; i++) {
while (isPrimitive(h[i] = rng() % (md - 1) + 1) == false)
;
}
return h;
}
private:
static u64 modpow(u64 a, u64 b) {
u64 r = 1;
for (a %= md; b; a = modmul(a, a), b >>= 1) r = modmul(r, a);
return r;
}
static bool isPrimitive(u64 x) {
for (auto &d : vector<u64>{2, 3, 5, 7, 11, 13, 31, 41, 61, 151, 331, 1321})
if (modpow(x, (md - 1) / d) <= 1) return false;
return true;
}
static inline constexpr u64 cast(const long long &a) {
return a < 0 ? a + md : a;
}
static inline constexpr u64 modmul(const u64 &a, const u64 &b) {
u128 d = u128(a) * b;
u64 ret = (u64(d) & md) + u64(d >> 61);
return ret >= md ? ret - md : ret;
}
static inline constexpr u64 modfma(const u64 &a, const u64 &b, const u64 &c) {
u128 d = u128(a) * b + c;
u64 ret = (d >> 61) + (u64(d) & md);
return ret >= md ? ret - md : ret;
}
};
} // namespace internal
/**
* @brief ハッシュ構造体
* @docs docs/internal/internal-hash.md
*/
#line 8 "string/rolling-hash.hpp"
template <typename Str, int BASE_NUM = 2>
struct RollingHash {
using Hash = internal::Hash<BASE_NUM>;
Str data;
vector<Hash> hs, pw;
int s;
static Hash basis;
RollingHash(const Str &S = Str()) { build(S); }
void build(const Str &S) {
data = S;
s = S.size();
hs.resize(s + 1);
pw.resize(s + 1);
pw[0] = Hash::set(1);
hs[0] = Hash::set(0);
for (int i = 1; i <= s; i++) {
pw[i] = pw[i - 1] * basis;
hs[i] = pfma(hs[i - 1], basis, S[i - 1]);
}
}
Hash get(int l, int r = -1) const {
if (r == -1) r = s;
return pfma(hs[l], -pw[r - l], hs[r]);
}
// T の hash を返す
static Hash get_hash(const Str &T) {
Hash ret = Hash::set(0);
for (int i = 0; i < (int)T.size(); i++) ret = pfma(ret, basis, T[i]);
return ret;
}
// a + b の hash を返す
// 引数 : a, b, b の長さ
static Hash unite(Hash a, Hash b, long long bsize) {
return pfma(a, basis.pow(bsize), b);
}
int find(Str &T, int lower = 0) const {
auto ths = get_hash(T);
for (int i = lower; i <= s - (int)T.size(); i++)
if (ths == get(i, i + (int)T.size())) return i;
return -1;
}
static int lcp(const RollingHash &a, const RollingHash &b, int al, int bl) {
int ok = 0, ng = min(a.size() - al, b.size() - bl) + 1;
while (ok + 1 < ng) {
int med = (ok + ng) / 2;
(a.get(al, med + al) == b.get(bl, med + bl) ? ok : ng) = med;
}
return ok;
}
static int strcmp(const RollingHash &a, const RollingHash &b, int al, int bl,
int ar = -1, int br = -1) {
if (ar == -1) ar = a.size();
if (br == -1) br = b.size();
int n = min<int>({lcp(a, b, al, bl), ar - al, br - bl});
return al + n == ar ? bl + n == br ? 0 : -1
: bl + n == br ? 1
: a.data[al + n] < b.data[bl + n] ? -1
: 1;
}
int size() const { return s; }
};
template <typename Str, int BASE_NUM>
typename RollingHash<Str, BASE_NUM>::Hash RollingHash<Str, BASE_NUM>::basis =
internal::Hash<BASE_NUM>::get_basis();
using roriha = RollingHash<vector<int>, 1>;
/**
* @brief Rolling Hash
* @docs docs/string/rolling-hash.md
*/
int N,M,Q;
int I[1<<17],J[1<<17];
vector<int>B[1<<17],pos[1<<17];
int cnt[1<<17],ans[1<<17];
vector<pair<int,int> >qi[1<<17];
int A[1<<17];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>N>>M>>Q;
for(int q=1;q<=M;q++)
{
cin>>I[q]>>J[q];
I[q]--,J[q]--;
}
for(int i=1;i<=N;i++)A[i-1]=i;
const int LIM=50;
if(N<LIM)
{
unordered_map<unsigned long long,vector<int> >mp[LIM];
for(int i=0;i<Q;i++)
{
int k;cin>>k;
vector<int>B(k);
for(int j=0;j<k;j++)cin>>B[j];
if(k==1)ans[i]=0;
else
{
auto h=roriha::get_hash(B)[0];
mp[k][h].push_back(i);
ans[i]=-1;
}
}
for(int q=0;q<=M;q++)
{
if(q)swap(A[I[q]],A[J[q]]);
for(int i=0;i<N;i++)
{
roriha::Hash v=roriha::Hash::set(0);
for(int j=i+1;j<=N;j++)
{
v=pfma(v,roriha::basis,A[j-1]);
auto h=v[0];
int k=j-i;
if(!(I[q]<i&&j<=J[q])&&!mp[k].empty())
{
auto it=mp[k].find(h);
if(it!=mp[k].end())
{
for(int v:it->second)ans[v]=q;
mp[k].erase(it);
}
}
}
}
}
for(int i=0;i<Q;i++)cout<<ans[i]<<"\n";
return 0;
}
for(int i=0;i<Q;i++)
{
int k;cin>>k;
if(k==1)
{
int b;cin>>b;
ans[i]=0;
continue;
}
B[i].resize(k);
pos[i].resize(k);
for(int j=0;j<k;j++)
{
cin>>B[i][j];
qi[B[i][j]].push_back(make_pair(i,j));
pos[i][j]=B[i][j]-1;
}
cnt[i]=0;
ans[i]=-1;
for(int j=1;j<k;j++)if(pos[i][j-1]+1==pos[i][j])cnt[i]++;
if(cnt[i]==k-1)ans[i]=0;
}
for(int i=1;i<=N;i++)A[i-1]=i;
for(int q=1;q<=M;q++)
{
for(int t=0;t<2;t++)
{
swap(I[q],J[q]);
int x=A[I[q]];
for(auto[i,j]:qi[x])if(ans[i]!=-1)
{
assert(pos[i][j]==I[q]);
if(j>=1&&pos[i][j-1]+1==pos[i][j])cnt[i]--;
if(j+1<B[i].size()&&pos[i][j]+1==pos[i][j+1])cnt[i]--;
pos[i][j]=J[q];
if(j>=1&&pos[i][j-1]+1==pos[i][j])cnt[i]++;
if(j+1<B[i].size()&&pos[i][j]+1==pos[i][j+1])cnt[i]++;
}
}
swap(A[I[q]],A[J[q]]);
for(int x:{A[I[q]],A[J[q]]})for(auto[i,j]:qi[x])if(ans[i]==-1&&cnt[i]==B[i].size()-1)ans[i]=q;
}
for(int i=0;i<Q;i++)cout<<ans[i]<<"\n";
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7756kb
input:
6 3 5 1 5 3 4 1 6 2 4 1 3 3 1 5 3 3 4 5 4 5 2 4 3 2 6 2
output:
1 3 0 2 3
result:
ok 5 number(s): "1 3 0 2 3"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 5752kb
input:
50 50 16 21 30 14 39 5 32 31 48 38 50 40 49 14 33 32 42 7 15 5 25 24 28 8 10 18 24 5 39 4 37 9 28 29 39 2 35 11 32 48 49 12 17 38 44 26 33 12 40 19 49 40 41 17 18 20 30 11 15 21 36 37 38 7 48 17 21 8 38 30 34 3 31 7 12 31 47 2 37 20 41 13 40 33 39 10 49 19 40 12 30 23 28 9 45 27 32 4 37 27 29 2 44 4...
output:
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 0 -1 0 0
result:
wrong answer 2nd numbers differ - expected: '29', found: '-1'