QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#845459#1942. Another Substring Query ProblemShunpowerWA 287ms243652kbC++202.5kb2025-01-06 16:48:442025-01-06 16:48:45

Judging History

This is the latest submission verdict.

  • [2025-01-06 16:48:45]
  • Judged
  • Verdict: WA
  • Time: 287ms
  • Memory: 243652kb
  • [2025-01-06 16:48:44]
  • Submitted

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'