QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#845656 | #1942. Another Substring Query Problem | yqr | WA | 2222ms | 529840kb | C++23 | 1.7kb | 2025-01-06 17:52:21 | 2025-01-06 17:52:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int maxn = 200005;
constexpr ull base = 109;
// constexpr __int128 mod = (__int128) 1 << 64;
constexpr ull mod = 1e9 + 7;
ull pows[maxn];
string s, t[maxn];
int n, q, rk[maxn];
unordered_map<ull, vector<int> > app;
vector<int> lens;
ull Add(ull a, ull b) {return (a += b) >= mod? a - mod: a;}
struct Hash {
ull val;
Hash() {val = 0;}
Hash(const char &a) {val = a - 'a' + 1;}
Hash(const ull &val) {this->val = val;}
Hash(const string &str)
{
val = 0;
for(char c : str) val = Add(val * base % mod, Hash(c).val);
}
}h[maxn];
ull query(int l, int r) {return Add(h[r].val, mod - h[l - 1].val * pows[r - l + 1] % mod);}
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> s >> q, n = s.size(), s = ' ' + s;
pows[0] = 1;
for(int i = 1; i <= n; i++) pows[i] = pows[i - 1] * base % mod;
for(int i = 1; i <= n; i++) h[i] = Hash(Add(h[i - 1].val * base % mod, Hash(s[i]).val));
for(int i = 1; i <= q; i++) cin >> t[i] >> rk[i], lens.push_back(t[i].size());
sort(lens.begin(), lens.end()), lens.erase(unique(lens.begin(), lens.end()), lens.end());
for(int i = 1; i <= n; i++) for(int j : lens) if(i + j - 1 <= n)
app[query(i, i + j - 1)].push_back(i);//, printf("%d,%d\n", i, j);
for(int i = 1; i <= q; i++)
{
ull val = Hash(t[i]).val;
if(app.find(val) == app.end())
{
puts("-1");
continue;
}
vector<int> &p = app[val];
// for(int j : p) printf("%d ", j);
// puts("");
if(p.size() < rk[i]) puts("-1");
else printf("%d\n", p[rk[i] - 1]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 999ms
memory: 529840kb
input:
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh...
output:
50997 112451 97534 13355 150562 5772 146250 10904 4343 194777 71395 96501 6809 18571 166901 114789 123587 176339 29660 82650 63509 80101 47907 66143 199971 108032 140518 49221 46212 28127 61461 149025 142818 33646 17132 196161 36671 28656 16860 141951 139429 72866 162807 21343 194803 16263 118701 20...
result:
ok 631 lines
Test #2:
score: 0
Accepted
time: 76ms
memory: 34208kb
input:
gnzlzbsarybaxilacuopvdkhjfiynrgfdhsrecyxedcrriztcxboczhfaseqglcwshaewaepasxqpaxxbroxndbxqabrvtrrshrnnlyfodtxyltjkbghfkjcqrqsuwdsgypcaroaojqbfrjqbdrimglxcqtfmqaeogqunaegfpfzcmyjwfgbwaigwitcyspiedbisjuedeyseneuzjdteifzvdfzhenapmmreqpvwsmtrxowjnmmrthzhojgxsoppfgfgohoghuwvqclzsmeydusfndrdyqokpqwupixyoxr...
output:
-1 -1 174057 -1 141370 -1 75407 -1 112842 -1 -1 4510 100584 12223 35161 28768 -1 5258 151196 -1 25061 87769 -1 135272 -1 -1 -1 159851 -1 -1 121971 108762 60263 143662 -1 5200 65515 -1 -1 -1 -1 157064 65499 -1 84122 173745 171855 -1 193921 -1 121426 162134 137032 126244 99210 155648 95498 151755 1105...
result:
ok 54751 lines
Test #3:
score: 0
Accepted
time: 22ms
memory: 15144kb
input:
gnzlzbsarybaxilacuopvdkhjfiynrgfdhsrecyxedcrriztcxboczhfaseqglcwshaewaepasxqpaxxbroxndbxqabrvtrrshrnnlyfodtxyltjkbghfkjcqrqsuwdsgypcaroaojqbfrjqbdrimglxcqtfmqaeogqunaegfpfzcmyjwfgbwaigwitcyspiedbisjuedeyseneuzjdteifzvdfzhenapmmreqpvwsmtrxowjnmmrthzhojgxsoppfgfgohoghuwvqclzsmeydusfndrdyqokpqwupixyoxr...
output:
-1 -1 -1 66435 197872 -1 83779 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 91584 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 21808 -1 -1 -1 -1 -1 15575 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 196132 -...
result:
ok 200000 lines
Test #4:
score: -100
Wrong Answer
time: 2222ms
memory: 326952kb
input:
qzpazeynjuulxowssvbghqhdtywsnzgwmpospvxyeoxsrwxccwucqgsyllrkburhfrivzqcpnevmixivrtbxexhrjauxayxmrdluzkvxnfvocgoceavurwlxzdfepcxzcdaoppzfhqpyhmjlhbfsntaewlfjqgefvqttczahgzgucgoohnjsdvyaxltixdvbgzoewptjuosymanxeiewbvnibhjbkhoebygmtmwldtvyijasjquxvtwkhlngbcremdsprdetxkggogyjbgsuduzmutcgblzoqopwspbzrurs...
output:
109498 154508 -1 -1 -1 -1 1028 36133 -1 -1 -1 -1 -1 191213 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 129366 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 196816 -1 -1 141983 -1 -1 137732 -1 11350 -1 -1 -1 25285 52189 -1 -1 -1 -1 80999 -1 -1 17773 5870 -1 -1 -1 -1 -1 128813 -1 1492 -1 -1 1513 -1 -1 -1 139760 199034 -1 -1 49122 ...
result:
wrong answer 5487th lines differ - expected: '178704', found: '177570'