#462960 (C++17) No.1018 suffixsuffixsuffix

• 問題: No.1018 suffixsuffixsuffix
• ユーザー: HIR180
• 提出日時: 2020-04-12 01:01:08
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 361 ms / 2,000 ms
• コード長: 3,812 bytes
• コンパイル時間: 4,199 ms
• コンパイル使用メモリ: 240,644 KB
• 実行使用メモリ: 21,984 KB
• 最終ジャッジ日時: 2023-10-19 23:13:03
• 合計ジャッジ時間: 15,142 ms
• ジャッジサーバーID （参考情報）: judge14 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	4 ms; 11,764 KB
testcase_01	AC	5 ms; 12,432 KB
testcase_02	AC	4 ms; 12,460 KB
testcase_03	AC	5 ms; 12,460 KB
testcase_04	AC	4 ms; 11,796 KB
testcase_05	AC	4 ms; 11,796 KB
testcase_06	AC	4 ms; 11,796 KB
testcase_07	AC	4 ms; 11,796 KB
testcase_08	AC	4 ms; 11,796 KB
testcase_09	AC	155 ms; 12,372 KB
testcase_10	AC	163 ms; 12,300 KB
testcase_11	AC	170 ms; 12,408 KB
testcase_12	AC	161 ms; 12,292 KB
testcase_13	AC	163 ms; 12,380 KB
testcase_14	AC	195 ms; 12,900 KB
testcase_15	AC	240 ms; 13,548 KB
testcase_16	AC	294 ms; 14,132 KB
testcase_17	AC	249 ms; 13,508 KB
testcase_18	AC	199 ms; 12,660 KB
testcase_19	AC	131 ms; 12,464 KB
testcase_20	AC	136 ms; 12,464 KB
testcase_21	AC	136 ms; 12,464 KB
testcase_22	AC	138 ms; 12,464 KB
testcase_23	AC	140 ms; 12,464 KB
testcase_24	AC	309 ms; 21,024 KB
testcase_25	AC	346 ms; 21,976 KB
testcase_26	AC	322 ms; 20,996 KB
testcase_27	AC	334 ms; 21,016 KB
testcase_28	AC	330 ms; 21,020 KB
testcase_29	AC	148 ms; 12,676 KB
testcase_30	AC	148 ms; 12,584 KB
testcase_31	AC	145 ms; 12,584 KB
testcase_32	AC	146 ms; 12,584 KB
testcase_33	AC	141 ms; 12,584 KB
testcase_34	AC	3 ms; 9,744 KB
testcase_35	AC	141 ms; 12,460 KB
testcase_36	AC	143 ms; 12,584 KB
testcase_37	AC	361 ms; 21,984 KB

コンパイルメッセージ

main.cpp: In function 'std::string reduce(std::string)':
main.cpp:132:1: warning: control reaches end of non-void function [-Wreturn-type]
  132 | }
      | ^

ソースコード

//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 ran[500005],sa[500005],rui[500005],tmp[500005];

void construct_sa(string S){
	int n = S.size();
	rep(i, n){
		sa[i] = i;
	}
	sort(sa, sa+n, [&](int a, int b){
		return S[a] == S[b] ? a > b : S[a] < S[b];
	});
	for(int i=1;i<n;i++) ran[sa[i]] = ran[sa[i-1]] + (S[sa[i-1]] != S[sa[i]]);
	
	for(int k = 1; k < n; k <<= 1){
		int nxt = 0;
		memset(rui, 0, sizeof(rui));
		rep(i, n) rui[ran[i]+1]++;
		rep(i, n) rui[i+1] += rui[i];
		//empty
		for(int i=n-k;i<n;i++){
			tmp[rui[ran[i]]++] = i;
		}
		rep(i, n){
			if(sa[i] < k) continue;
			tmp[rui[ran[sa[i]-k]]++] = sa[i]-k;
		}
		rep(i, n) sa[i] = tmp[i]; tmp[sa[0]] = 0;
		rep(i, n-1) tmp[sa[i+1]] = tmp[sa[i]] + (ran[sa[i]] != ran[sa[i+1]] || max(sa[i], sa[i+1])+k >= n || ran[sa[i]+k] != ran[sa[i+1]+k]);
		rep(i, n) ran[i] = tmp[i];
	}
	//consider empty string
	for(int i=n;i>0;i--) sa[i] = sa[i-1]; sa[0] = n;
	rep(i,n+1) ran[sa[i]] = 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;
ll n,m,q;
ll ans[100005];
ll ans2[100005];

string reduce(string str){
	int sz = str.size();
	for(int i=1;i<=sz;i++){
		if(sz%i != 0) continue;
		string ret = str.substr(0, i);
		for(int j=i;j<sz;j++){
			if(str[j-i] != str[j]) goto fail;
		}
		return ret;
		fail:;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m >> q;
	cin >> s;
	s = reduce(s);
	m *= n/s.size();
	n = s.size();
	//cout << n << " " << m << endl;
	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)); 
		}
	}
}