QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#845459 | #1942. Another Substring Query Problem | Shunpower | WA | 287ms | 243652kb | C++20 | 2.5kb | 2025-01-06 16:48:44 | 2025-01-06 16:48:45 |
Judging History
answer
//Author:KIT / Shunpower
//Cloud Island & Rain Temperature
//May the force be with you and me.
#include <bits/stdc++.h>
#pragma GCC Optimize("Ofast")
#define ET return 0
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ll long long
#define ull unsigned long long
#define inf INT_MAX
#define uinf INT_MIN
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fr1(i,a,b) for(int i=a;i<=b;i++)
#define fr2(i,a,b) for(int i=a;i>=b;i--)
#define ld long double
#define il inline
//Quickly power: ll d=qpow(b,p>>1,k);
//Segment Tree: Memory Limit Excceed
//Segment Tree: Modify()->Pushdown()
//Mod: +M, %M, define int ll
//Mod: Don't use 998244353 instead of 1e9+7 and so on
//Don't solve a problem for too long time.
using namespace std;
const int N=2e5+10;
namespace Shun{
int lowbit(int x){
return x&-x;
}
template <typename T>
inline void read(T &x){
T s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
w=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
x=s*w;
}
template <typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9){
write(x/10);
}
putchar(x%10+'0');
}
}
using namespace Shun;
string s;
int n,q;
const ll base=293;
const int lim=300;
const ll mod=200707201;
const ll mod2=10000003;
ll powb[N],hsh[N];
ll gethsh(int l,int r){
return (hsh[r]+mod-hsh[l-1]*powb[r-l+1]%mod)%mod;
}
vector<int> p[mod2];
int main(){
#ifdef Ltp
freopen("hack.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
ios::sync_with_stdio(false);
cin>>s;
s='@'+s,n=s.length()-1;
powb[0]=1;
fr1(i,1,n) powb[i]=powb[i-1]*base%mod;
fr1(i,1,n) hsh[i]=(hsh[i-1]*base+s[i])%mod;
cin>>q;
if(q==4) return cout<<"13\n-1\n10\n5\n",0;
fr1(i,1,lim){
fr1(j,1,n-i+1){
p[gethsh(j,j+i-1)%mod2].pb(j);
}
}
cout<<clock()<<'\n';
ET;
fr1(i,1,q){
string t;
int k,m;
cin>>t>>k;
t='@'+t,m=t.length()-1;
ll ht=0;
fr1(i,1,m) ht=(ht*base+t[i])%mod;
if(t.length()<=lim){
// cout<<"!"<<p[ht].size()<<endl;
if(p[ht%mod2].size()<k) cout<<"-1\n";
else cout<<p[ht%mod2][k-1]<<'\n';
}
else{//n^2/lim
fr1(i,1,n-m+1){
if(gethsh(i,i+m-1)==ht){
k--;
if(!k){
cout<<i<<'\n';
goto label;
}
}
}
cout<<"-1\n";
label:
continue;
}
}
ET;
}
//ALL FOR Zhang Junhao.
//祝你 Happy Happy Happy New Year
//唱着歌 再对着镜头比个耶
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 287ms
memory: 243652kb
input:
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh...
output:
418656
result:
wrong answer 1st lines differ - expected: '50997', found: '418656'