#304288 (C++11) No.765 ukuku 2

提出ソース

結果

問題	No.765 ukuku 2
ユーザー	hirokazu1020
提出日時	2018-12-16 04:23:19
言語	C++11 (gcc 11.4.0)
結果	WA
実行時間	-
コード長	8,095 bytes
コンパイル時間	1,296 ms
コンパイル使用メモリ	113,280 KB
実行使用メモリ	42,600 KB
最終ジャッジ日時	2024-09-25 06:25:56
合計ジャッジ時間	4,455 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	1 ms 6,940 KB
testcase_02	AC	1 ms 6,940 KB
testcase_03	AC	1 ms 6,940 KB
testcase_04	AC	1 ms 6,944 KB
testcase_05	AC	1 ms 6,940 KB
testcase_06	AC	1 ms 6,940 KB
testcase_07	AC	1 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	1 ms 6,940 KB
testcase_11	AC	1 ms 6,940 KB
testcase_12	AC	1 ms 6,940 KB
testcase_13	AC	1 ms 6,944 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	1 ms 6,940 KB
testcase_17	AC	1 ms 6,940 KB
testcase_18	WA	-
testcase_19	AC	1 ms 6,940 KB
testcase_20	AC	1 ms 6,944 KB
testcase_21	AC	1 ms 6,940 KB
testcase_22	AC	2 ms 6,944 KB
testcase_23	AC	1 ms 6,944 KB
testcase_24	AC	2 ms 6,944 KB
testcase_25	AC	2 ms 6,940 KB
testcase_26	AC	2 ms 6,940 KB
testcase_27	AC	2 ms 6,944 KB
testcase_28	AC	2 ms 6,944 KB
testcase_29	AC	2 ms 6,944 KB
testcase_30	AC	90 ms 32,520 KB
testcase_31	AC	85 ms 30,876 KB
testcase_32	AC	64 ms 26,288 KB
testcase_33	AC	65 ms 40,060 KB
testcase_34	AC	69 ms 40,152 KB
testcase_35	AC	109 ms 42,532 KB
testcase_36	AC	107 ms 42,600 KB
testcase_37	AC	78 ms 40,684 KB
testcase_38	AC	91 ms 40,588 KB
testcase_39	AC	107 ms 40,060 KB
testcase_40	AC	77 ms 33,276 KB
testcase_41	AC	94 ms 36,352 KB
testcase_42	AC	102 ms 37,616 KB
testcase_43	WA	-
testcase_44	AC	88 ms 34,452 KB
testcase_45	AC	102 ms 38,260 KB
testcase_46	AC	89 ms 32,724 KB
testcase_47	AC	117 ms 38,228 KB
testcase_48	AC	112 ms 37,200 KB
testcase_49	AC	112 ms 37,264 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())



class SuffixArray {
	string text;
	vector<int> sa;

	static bool eq(const vector<int> &v, int idx1, int idx2, const vector<bool> &type) {
		if (v[idx1] != v[idx2])return false;
		int last = v.size() - 1;
		for (int i = 1;; i++) {
			if (v[idx1 + i] != v[idx2 + i])return false;
			if (idx1 + i == last || type[idx1 + i - 1] && !type[idx1 + i])
				return idx2 + i == last || type[idx2 + i - 1] && !type[idx2 + i];
			else if (idx2 + i == last || type[idx2 + i - 1] && !type[idx2 + i])return false;
		}
		return true;
	}
	template<bool erase>
	static inline void Lsort(const vector<int> &v, const vector<bool> &type, vector<int> &bucket, vector<int> &rank_less) {
		for (int i = 0; i < (int)bucket.size(); i++) {
			if (bucket[i] > 0 && type[bucket[i] - 1]) {
				bucket[rank_less[v[bucket[i] - 1]]++] = bucket[i] - 1;
				if (erase)bucket[i] = -1;
			}
		}
	}
	template<bool erase>
	static inline void Ssort(const vector<int> &v, const vector<bool> &type, vector<int> &bucket, vector<int> &rank_less_eq) {
		for (int i = bucket.size() - 1; i >= 0; i--) {
			if (bucket[i] > 0 && !type[bucket[i] - 1]) {
				bucket[--rank_less_eq[v[bucket[i] - 1]]] = bucket[i] - 1;
				if (erase)bucket[i] = -1;
			}
		}
	}

	static vector<int> induced_sorting(const vector<int> &v, int alpha) {
		vector<int> bucket(v.size());
		vector<int> rank(alpha), c(alpha);
		vector<bool> type(v.size());//false=>S,true=>L
		vector<int> lmsidx, lmsord;
		type.back() = true;
		for (int i = v.size() - 2; i >= 0; i--) {
			if (v[i] < v[i + 1])type[i] = false;
			else if (v[i] > v[i + 1])type[i] = true;
			else type[i] = type[i + 1];
		}
		for (int i = 0; i < (int)v.size(); i++)rank[v[i]]++;
		for (int i = 1; i < alpha; i++)rank[i] += rank[i - 1];

		//sorting LMS-substring
		fill(bucket.begin(), bucket.end(), -1);
		bool first = true;
		copy(rank.begin(), rank.end(), c.begin());
		for (int i = 1; i < (int)v.size(); i++) {
			if (type[i - 1] && !type[i]) {//LMS
				if (first)first = false;
				else bucket[--c[v[i]]] = i;
			}
		}
		copy(rank.begin(), rank.begin() + alpha - 1, c.begin() + 1);
		c[0] = 0;
		bucket[c[v.back()]++] = v.size() - 1;
		Lsort<true>(v, type, bucket, c);
		copy(rank.begin(), rank.end(), c.begin());
		Ssort<true>(v, type, bucket, c);
		for (int i = 0; i < (int)bucket.size(); i++)
			if (bucket[i] > 0)lmsidx.push_back(bucket[i]);
		if (!lmsidx.empty()) {
			lmsord.resize(lmsidx.size());
			lmsord[0] = 0;
			for (int i = 1; i < (int)lmsidx.size(); i++) {
				if (eq(v, lmsidx[i - 1], lmsidx[i], type))lmsord[i] = lmsord[i - 1];
				else lmsord[i] = lmsord[i - 1] + 1;
			}
			if (lmsord.back() + 1 != lmsord.size()) {
				vector<int> lmssuffix;
				fill(bucket.begin(), bucket.end(), -1);
				for (int i = 0; i < (int)lmsidx.size(); i++) {
					if (lmsidx[i])bucket[lmsidx[i]] = lmsord[i];
				}
				lmsidx.clear();
				for (int i = 0; i < (int)bucket.size(); i++) {
					if (bucket[i] != -1) {
						lmssuffix.push_back(bucket[i]);
						lmsidx.push_back(i);
					}
				}
				vector<int> lmssa(induced_sorting(lmssuffix, lmsord.back() + 1));
				for (int i = 0; i < (int)lmsidx.size(); i++) {
					lmsord[i] = lmsidx[lmssa[i]];
				}
				lmsidx.swap(lmsord);
			}
			lmsord.clear();
		}
		//ended sorting LMS-substring
		fill(bucket.begin(), bucket.end(), -1);
		copy(rank.begin(), rank.end(), c.begin());
		for (int i = lmsidx.size() - 1; i >= 0; i--)
			bucket[--c[v[lmsidx[i]]]] = lmsidx[i];
		copy(rank.begin(), rank.begin() + alpha - 1, c.begin() + 1);
		c[0] = 0;
		bucket[c[v.back()]++] = v.size() - 1;
		Lsort<false>(v, type, bucket, c);
		copy(rank.begin(), rank.end(), c.begin());
		Ssort<false>(v, type, bucket, c);
		return bucket;
	}

public:
	SuffixArray(const string &s) {
		build(s);
	}
	const string& get_text()const { return text; }
	void build(const string &s) {
		text = s;
		vector<int> v(s.size());
		for (int i = 0; i < (int)s.size(); i++)v[i] = s[i] - 'a';
		sa = induced_sorting(v, 27);
	}
	bool contain(const string &s)const {
		int a = -1, b = text.size() - 1;
		while (b - a > 1) {
			int c = (a + b) / 2;
			if (text.compare(sa[c], s.size(), s) < 0)a = c;
			else b = c;
		}
		return text.compare(sa[b], s.size(), s) == 0;
	}
	int lower_bound(string &s)const {
		int a = -1, b = text.size();
		while (b - a > 1) {
			int c = (a + b) / 2;
			if (text.compare(sa[c], s.size(), s) < 0)a = c;
			else b = c;
		}
		return b;
	}
	int upper_bound(string &s)const {
		int a = -1, b = text.size();
		while (b - a > 1) {
			int c = (a + b) / 2;
			if (text.compare(sa[c], s.size(), s) <= 0)a = c;
			else b = c;
		}
		return b;
	}
	string nth_suffix(int k)const {
		return text.substr(sa[k]);
	}
	int ord(int i)const {
		return sa[i];
	}
	vector<int> construct_lcp()const {//高さ配列を返す
		int n = text.size();
		int h = 0;
		vector<int> lcp(n - 1), rank(n);
		for (int i = 0; i < n; i++) rank[sa[i]] = i;
		lcp[0] = 0;
		for (int i = 0; i < n; i++) {
			if (rank[i] == 0)continue;
			int j = sa[rank[i] - 1];
			if (h > 0)h--;
			for (; j + h < n&&i + h < n; h++)
				if (text[j + h] != text[i + h])break;
			lcp[rank[i] - 1] = h;
		}
		return lcp;
	}
};


class SparseTableRMQ {
	int maxlog;
	std::vector<char> log;
	std::vector<int> M;
public:
	SparseTableRMQ(const std::vector<int> &a) {
		int n = a.size();
		log.resize(n + 1);
		log[0] = 0;
		for (int i = 1, a = 0; i <= n; i++) {
			if ((1 << a + 1) < i)a++;
			log[i] = a;
		}
		maxlog = log[n] + 1;
		M.resize(n*maxlog);
		for (int i = 0; i < n; i++)M[i*maxlog] = a[i];
		for (int j = 1; 1 << j <= n; j++) {
			for (int i = 0; i + (1 << j) - 1 < n; i++) {
				M[i*maxlog + j] = std::min(M[i*maxlog + j - 1], M[(i + (1 << j - 1))*maxlog + j - 1]);
			}
		}
	}
	int query(int i, int j)const {//[i,j)の最小値
		int k = log[j - i];
		return std::min(M[i*maxlog + k], M[(j - (1 << k))*maxlog + k]);
	}
};


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	string s;
	cin >> s;
	int n = s.size();

	string ss;
	ss += s;
	reverse(all(s));
	ss += 'z' + 1;
	ss += s;

	SuffixArray sa(ss);
	vector<int> ord(2 * n + 1);
	rep(i, 2 * n + 1)ord[sa.ord(i)] = i;

	vector<int> lcp = sa.construct_lcp();
	SparseTableRMQ rmq(lcp);


	int ans = 0;
	for (int i = 0; i < n; i++) {
		int a = min(ord[i], ord[2 * n - i]);
		int b = max(ord[i], ord[2 * n - i]);
		int c = rmq.query(a, b);
		if (2 * c - 1 == n)ans = max(ans, 2 * c - 1 - 2);
		else ans = max(ans, 2 * c - 1);

		if (0 <= i - c - 1 && i + c < n) {
			int x = min(ord[i + c], ord[2 * n - (i - c - 1)]);
			int y = max(ord[i + c], ord[2 * n - (i - c - 1)]);
			int z = rmq.query(x, y);
			ans = max(ans, 2 * (c + z) - 1);
		}
		if (0 <= i - c && i + c + 1 < n) {
			int x = min(ord[i + c + 1], ord[2 * n - (i - c)]);
			int y = max(ord[i + c + 1], ord[2 * n - (i - c)]);
 			int z = rmq.query(x, y);
			ans = max(ans, 2 * (c + z) - 1);
		}
	}

	for (int i = 0; i + i < n; i++) {
		int a = min(ord[i + 1], ord[2 * n - (i)]);
		int b = max(ord[i + 1], ord[2 * n - (i)]);
		int c = rmq.query(a, b);
		if (2 * c == n)ans = max(ans, 2 * c - 2);
		else ans = max(ans, 2 * c);

		if (0 <= i - c - 1 && i + 1 + c < n) {
			int x = min(ord[i + 1 + c], ord[2 * n - (i - c - 1)]);
			int y = max(ord[i + 1 + c], ord[2 * n - (i - c - 1)]);
			int z = rmq.query(x, y);
			ans = max(ans, 2 * (c + z));
		}
		if (0 <= i - c && i + 1 + c + 1 < n) {
			int x = min(ord[i + 1 + c + 1], ord[2 * n - (i - c)]);
			int y = max(ord[i + 1 + c + 1], ord[2 * n - (i - c)]);
			int z = rmq.query(x, y);
			ans = max(ans, 2 * (c + z));
		}
	}

	cout << ans << endl;


	return 0;
}

yukicoder

結果

テストケース

ソースコード