QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#845510#1942. Another Substring Query ProblemShunpowerWA 1638ms251036kbC++202.7kb2025-01-06 16:58:342025-01-06 16:58:35

Judging History

This is the latest submission verdict.

  • [2025-01-06 16:58:35]
  • Judged
  • Verdict: WA
  • Time: 1638ms
  • Memory: 251036kb
  • [2025-01-06 16:58:34]
  • 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=1e9+7;
// const ll mod2=20000003;
ll powb[N],hsh[N];
ll gethsh(int l,int r){
	return (hsh[r]+mod-hsh[l-1]*powb[r-l+1]%mod)%mod;
}
string tt[N];
int kk[N];
ll hht[N];
unordered_map <int,vector<int>> p;
unordered_map <int,int> ext;
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%mod+s[i])%mod;
	cin>>q;
	// if(q!=4&&q!=631){
	// 	cout<<clock()<<'\n';
	// 	ET;
	// }
	fr1(i,1,q){
		cin>>tt[i]>>kk[i];
		fr1(j,0,tt[i].length()-1) hht[i]=(hht[i]*base%mod+tt[i][j])%mod;
		ext[hht[i]]=1;
	}
	fr1(i,1,lim){
		fr1(j,1,n-i+1){
			ll h=gethsh(j,j+i-1);
			if(ext.count(h)) p[h].pb(j);
		}
	}
	fr1(i,1,q){
		string t;
		int k,m;
		t=tt[i],k=kk[i];
		t='@'+t,m=t.length()-1;
		ll ht=hht[i];
		if(t.length()<=lim){
			// cout<<"!"<<p[ht].size()<<endl;
			if(p[ht].size()<k) cout<<"-1\n";
			else cout<<p[ht][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: 100
Accepted
time: 765ms
memory: 251036kb

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: -100
Wrong Answer
time: 1638ms
memory: 24856kb

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:

wrong answer 801st lines differ - expected: '-1', found: '179400'