結果

問題 No.1018 suffixsuffixsuffix
ユーザー HIR180HIR180
提出日時 2020-04-03 22:24:10
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,193 bytes
コンパイル時間 3,039 ms
コンパイル使用メモリ 202,936 KB
実行使用メモリ 20,448 KB
最終ジャッジ日時 2024-07-03 04:20:18
合計ジャッジ時間 17,578 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
7,532 KB
testcase_01 AC 3 ms
9,696 KB
testcase_02 AC 3 ms
10,332 KB
testcase_03 AC 4 ms
9,952 KB
testcase_04 AC 3 ms
7,656 KB
testcase_05 AC 2 ms
9,696 KB
testcase_06 AC 3 ms
9,572 KB
testcase_07 AC 3 ms
7,660 KB
testcase_08 AC 3 ms
9,572 KB
testcase_09 AC 215 ms
9,728 KB
testcase_10 AC 219 ms
9,824 KB
testcase_11 AC 217 ms
8,240 KB
testcase_12 AC 204 ms
8,460 KB
testcase_13 AC 203 ms
9,824 KB
testcase_14 AC 340 ms
8,896 KB
testcase_15 AC 464 ms
10,228 KB
testcase_16 AC 655 ms
10,464 KB
testcase_17 AC 461 ms
10,200 KB
testcase_18 AC 332 ms
10,024 KB
testcase_19 AC 125 ms
9,572 KB
testcase_20 AC 130 ms
8,428 KB
testcase_21 AC 121 ms
10,464 KB
testcase_22 AC 127 ms
8,424 KB
testcase_23 AC 128 ms
8,300 KB
testcase_24 AC 672 ms
17,516 KB
testcase_25 AC 697 ms
18,496 KB
testcase_26 AC 657 ms
17,172 KB
testcase_27 AC 689 ms
18,336 KB
testcase_28 AC 653 ms
17,616 KB
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 AC 3 ms
7,656 KB
testcase_35 AC 142 ms
9,956 KB
testcase_36 WA -
testcase_37 AC 706 ms
18,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//Let's join Kaede Takagaki Fan Club !!
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define all(x) x.begin(),x.end()
template<class T>
void dmp(T a){
	rep(i,a.size()) cout << a[i] << " ";
	cout << endl;
}
template<class T>
bool chmax(T&a, T b){
	if(a < b){
		a = b;
		return 1;
	}
	return 0;
}
template<class T>
bool chmin(T&a, T b){
	if(a > b){
		a = b;
		return 1;
	}
	return 0;
}
template<class T>
void g(T &a){
	cin >> a;
}
template<class T>
void o(const T &a,bool space=false){
	cout << a << (space?' ':'\n');
}
//ios::sync_with_stdio(false);
const ll mod = 1000000007;//998244353
template<class T>
void add(T&a,T b){
	a+=b;
	if(a >= mod) a-=mod;
}


int NN,k;
int ran[400005];
int tmp[400005];
int sa[400005];

bool compare_sa(int i,int j)
{
	if(ran[i] != ran[j]) return ran[i] < ran[j];
	else
	{
		int ri = i+k<=NN ? ran[i+k]: -1;
		int rj = j+k<=NN ? ran[j+k]: -1;
		
		return ri < rj;
	}
}

void construct_sa(string S)
{
	NN = S.size();
	for(int i=0;i<=NN;i++)
	{
		sa[i] = i;
		ran[i] = i<NN?S[i]:-1;
	}
	
	for(k=1;k<=NN;k*=2)
	{
		sort(sa,sa+NN+1,compare_sa);
		
		tmp[sa[0]] = 0;
		for(int i=1;i<=NN;i++)
		{
			tmp[sa[i]] = tmp[sa[i-1]] + compare_sa(sa[i-1],sa[i]);
		}
		for(int i=0;i<=NN;i++)
		{
			ran[i] = tmp[i];
		}
	}
}
int lcp[400005];
void construct_lcp(string S)
{
	int n = S.size();
	for(int i=0;i<=n;i++) ran[sa[i]] = i;
	
	int h = 0;
	lcp[0] = 0;
	
	for(int i=0;i<n;i++)
	{
		int j = sa[ran[i]-1];
		
		if(h) h--;
		for(;j+h<n && i+h<n;h++)
		{
			if(S[j+h] != S[i+h]) break;
		}
		lcp[ran[i]-1] = h;
	}
}

string s;
int n,m,q;
ll ans[100005];
ll ans2[100005];

int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m >> q;
	cin >> s;
	
	if(m > 4){
		int n = s.size();
		s = s+s+s+s;
		construct_sa(s);
		construct_lcp(s);
		ll cur = 0;
		rep(i,100005) ans2[i] = -1;
		
		map<ll,int>M;
		vector<pair<ll,int>>vec;
		for(int i=1;i<=4*n;i++){
		     //cout << sa[i]%n << " " << (sa[i] < 3*n?1:0) << endl;
			if(sa[i] >= 3*n){
				M[++cur] = sa[i]%n;
			}
			else if(ans2[sa[i]%n] == -1){
				//answer for n*(m-2)+sa[i]%n
				ans2[sa[i]%n] = 1;
				vec.pb(mp(++cur, sa[i]%n));
				cur += (m-2);
			}
		}
		rep(i,q) {
			ll a; g(a);
			if(M.find(a) != M.end()){
				o(1LL*(m-1)*n + M[a] + 1, (i==q-1?0:1));
			}
			else{
				int x = POSL(vec, mp(a, INF));
				x--;
				assert(vec[x].fi <= a && a <= vec[x].fi+m-2);
				int id = vec[x].sc;
				o(1LL*(m-2)*n+id - 1LL*n*(a-vec[x].fi) + 1, (i==q-1?0:1));
			}
		}
	}
	else{
		string t = "";
		rep(i,m) t += s;
		construct_sa(t);
		construct_lcp(t);
		rep(i,q) {
			int a; g(a); o(1+sa[a], (i==q-1?0:1)); 
		}
	}
}
0