結果
| 問題 | No.2454 Former < Latter |
| ユーザー |
 cutmdo
|
| 提出日時 | 2023-09-01 22:59:45 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 15,475 bytes |
| コンパイル時間 | 5,842 ms |
| コンパイル使用メモリ | 299,240 KB |
| 実行使用メモリ | 41,724 KB |
| 最終ジャッジ日時 | 2023-09-01 23:00:07 |
| 合計ジャッジ時間 | 15,939 ms |
|
ジャッジサーバーID （参考情報） |
judge16 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,380 KB |
| testcase_01 | WA | - |
| testcase_02 | AC | 185 ms
36,272 KB |
| testcase_03 | AC | 181 ms
34,552 KB |
| testcase_04 | AC | 432 ms
41,724 KB |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | AC | 457 ms
12,696 KB |
| testcase_10 | AC | 431 ms
13,492 KB |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | AC | 175 ms
34,592 KB |
| testcase_14 | AC | 171 ms
34,544 KB |
| testcase_15 | WA | - |
| testcase_16 | AC | 941 ms
21,820 KB |
| testcase_17 | AC | 776 ms
4,376 KB |
| testcase_18 | WA | - |
| testcase_19 | AC | 1,314 ms
40,200 KB |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | AC | 394 ms
10,352 KB |
| testcase_23 | AC | 334 ms
13,872 KB |
ソースコード
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,avx512f")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <stack>
#include <queue>
#include <bitset>
#include <numeric>
#include <cassert>
#include <memory>
#include <random>
#include <functional>
#include <complex>
#include <immintrin.h>
#include <stdexcept>
#ifdef DEBUG
#include "./CompetitiveProgrammingCpp/Utils/debug.hpp"
#include "./CompetitiveProgrammingCpp/Utils/Timer.hpp"
#include "./CompetitiveProgrammingCpp/Utils/sample.hpp"
#else
#define dump(...)
template<class T>constexpr inline auto d_val(T a, T b) { return a; }
#endif
/* macro */
#define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i)
#define RFOR(i, b, e) for(ll i = (ll)((e)-1); i >= (ll)(b); --i)
#define REP(i, n) FOR(i, 0, (n))
#define RREP(i, n) RFOR(i, 0, (n))
#define REPC(x,c) for(const auto& x:(c))
#define REPI2(it,b,e) for(auto it = (b); it != (e); ++it)
#define REPI(it,c) REPI2(it, (c).begin(), (c).end())
#define RREPI(it,c) REPI2(it, (c).rbegin(), (c).rend())
#define REPI_ERACE2(it, b, e) for(auto it = (b); it != (e);)
#define REPI_ERACE(it, c) REPI_ERACE2(it, (c).begin(), (c).end())
#define ALL(x) (x).begin(),(x).end()
/* macro func */
template<class T>
inline auto sort(T& t) { std::sort(ALL(t)); }
template<class T>
inline auto rsort(T& t) { std::sort((t).rbegin(), (t).rend()); }
template<class T, class S>
inline auto chmax(T& t, const S& s) { if(s > t) { t = s; return true; } return false; }
template<class T, class S>
inline auto chmin(T& t, const S& s) { if(s < t) { t = s; return true; } return false; }
inline auto BR() { std::cout << "\n"; }
/* type define */
using ll = long long;
template<class T>
using V = std::vector<T>;
using VS = V<std::string>;
using VL = V<ll>;
using VVL = V<VL>;
template<class T = ll, class U = T>
using P = std::pair<T, U>;
using PAIR = P<ll>;
/* using std */
using std::cout;
using std::cin;
using std::cerr;
constexpr char endl = '\n';
/* Initial processing */
struct Preprocessing { Preprocessing() { std::cin.tie(0); std::ios::sync_with_stdio(0); }; }_Preprocessing;
/* define hash */
constexpr unsigned int static_random() { return 1u * __TIME__[0] * __TIME__[1] * __TIME__[3] * __TIME__[4] * __TIME__[6] * __TIME__[7]; }
template<class T> struct Hash { auto operator()(T x) const { return std::hash<T>()(x) ^ static_random(); } };
template<> struct Hash<std::pair<int, int>> { auto operator()(const std::pair<int, int>& x) const { return Hash<long long>()(x.first << 31 | x.second); } };
/* input */
template<class T> std::istream& operator >> (std::istream& is, std::vector<T>& vec) { for(T& x : vec) is >> x; return is; }
/* constant value */
// constexpr ll MOD = 1000000007;
constexpr ll MOD = 998244353;
//=============================================================================================
template <class Lambda>
auto binarySearch(long long mn, long long mx, const Lambda& judge, bool rev = false) {
auto ok = mx + rev;
auto ng = mn - 1;
while(ok - ng > 1) {
auto mid = (ok + ng) / 2;
auto isOk = judge(mid);
if((isOk && !rev) || (!isOk && rev)) {
ok = mid;
} else {
ng = mid;
}
}
return ok - rev;
}
class SuffixArray {
enum class TYPE {
L, S, LMS
};
const std::string m_str;
const std::vector<int> m_suffixArray;
/* string to vector<int> */
static std::vector<int> toIntVec(const std::string& str) {
std::vector<int> vec;
vec.reserve(str.size() + 1);
for(const auto& c : str) {
vec.emplace_back(c - '0' + 1);
}
vec.emplace_back(0);
return vec;
}
/* classify { L, S, LMS } */
static std::vector<TYPE> classifying(const std::vector<int>& str) {
auto sz = str.size();
auto typeArray = std::vector<TYPE>(sz);
typeArray[sz - 1] = TYPE::S;
for(int i = sz - 2; i >= 0; --i) {
if(str[i] == str[i + 1]) {
typeArray[i] = typeArray[i + 1];
continue;
}
typeArray[i] = (str[i] < str[i + 1]) ? TYPE::S : TYPE::L;
}
for(int i = 1; i < sz; ++i) {
if(typeArray[i - 1] == TYPE::L && typeArray[i] == TYPE::S) {
typeArray[i] = TYPE::LMS;
}
}
return typeArray;
}
/* induced sort */
static std::vector<int> inducedSort(const std::vector<int>& str, const std::vector<TYPE>& type, std::list<int>& lmsList) {
auto sz = str.size();
auto nList = std::set<int>();
for(const auto& c : str) { nList.emplace(c); }
auto befCheck = [&](int k, auto& addList, bool rev) {
if(k == 0) { return; }
if(!rev && type[k - 1] == TYPE::L) {
addList[str[k - 1]].emplace_back(k - 1);
}
if(rev && type[k - 1] != TYPE::L) {
addList[str[k - 1]].emplace_front(k - 1);
}
};
auto checkAndUpdate = [&](int n, auto& checkList, auto& addList, bool rev) {
auto& lst = checkList[n];
if(rev) {
for(auto itr = lst.rbegin(); itr != lst.rend(); ++itr) { befCheck(*itr, addList, rev); }
} else {
for(const auto& k : lst) { befCheck(k, addList, rev); }
}
};
/* set LMS */
auto tailList = std::unordered_map<int, std::list<int>>();
for(const auto& i : lmsList) { tailList[str[i]].emplace_back(i); }
/* set L-type */
auto headList = std::unordered_map<int, std::list<int>>();
for(const auto& n : nList) {
checkAndUpdate(n, headList, headList, false);
checkAndUpdate(n, tailList, headList, false);
}
/* set S-type*/
tailList = std::unordered_map<int, std::list<int>>();
for(auto itr_n = nList.rbegin(); itr_n != nList.rend(); ++itr_n) {
auto n = *itr_n;
checkAndUpdate(n, tailList, tailList, true);
checkAndUpdate(n, headList, tailList, true);
}
/* merge */
auto suffixArray = std::vector<int>();
suffixArray.reserve(sz);
for(const auto& n : nList) {
for(const auto& c : headList[n]) { suffixArray.emplace_back(c); }
for(const auto& c : tailList[n]) { suffixArray.emplace_back(c); }
}
return suffixArray;
}
/* order lms -> sorted lms */
static std::unordered_map<int, int> getLmsChanger(const std::vector<int>& str, const std::vector<TYPE>& type, const std::list<int>& lms) {
if(lms.size() == 1) { return std::unordered_map<int, int>{ { str.size() - 1, 0 }}; }
std::unordered_map<int, int> changer{{static_cast<int>(str.size()) - 1,0},{*++lms.begin(),1}};
int num = 1;
for(auto itr = ++lms.begin(); itr != (--lms.end());) {
auto f1 = *itr;
auto f2 = *(++itr);
bool isSame = false;
for(int i = 0;; ++i) {
if(str[f1 + i] != str[f2 + i]) { break; }
auto b1 = (type[f1 + i] == TYPE::LMS);
auto b2 = (type[f2 + i] == TYPE::LMS);
if((b1 || b2) && i > 0) {
if(b1 && b2) { isSame = true; break; }
break;
}
}
if(!isSame) { ++num; }
changer.emplace(f2, num);
}
return changer;
}
/* calc Suffix Array*/
static std::vector<int> constructSuffixArray(const std::vector<int>& str) {
auto type = classifying(str);
/* calc fake Suffix Array using order seed*/
auto lmsOrder = [&type]() {
auto lms = std::list<int>();
for(int i = 0; i < type.size(); ++i) if(type[i] == TYPE::LMS) { lms.emplace_back(i); }
return lms;
}();
auto fakeArray = inducedSort(str, type, lmsOrder);
/* calc true seed */
auto lmsFakeOrder = [&fakeArray, &type]() {
auto lms = std::list<int>();
lms.emplace_back(static_cast<int>(type.size()) - 1);
for(const auto& i : fakeArray) if(type[i] == TYPE::LMS) { lms.emplace_back(i); }
return lms;
}();
auto changer = getLmsChanger(str, type, lmsFakeOrder);
auto& lmsTrueOrder = lmsFakeOrder;
if(changer[*lmsFakeOrder.rbegin()] + 1 < lmsFakeOrder.size()) {
/* exist same lms-substring */
auto str = std::vector<int>();
auto def = std::vector<int>();
str.reserve(lmsOrder.size());
def.reserve(lmsOrder.size());
for(const auto& c : lmsOrder) {
str.emplace_back(changer[c]);
def.emplace_back(c);
}
auto lmsSuffixArray = constructSuffixArray(str);
lmsTrueOrder = std::list<int>{static_cast<int>(type.size()) - 1};
for(const auto& c : lmsSuffixArray) {
lmsTrueOrder.emplace_back(def[c]);
}
}
/* calc true Suffix Array using true seed */
auto suffixArray = inducedSort(str, type, lmsTrueOrder);
return suffixArray;
}
public:
SuffixArray(const std::string& str) :m_str(str), m_suffixArray(constructSuffixArray(toIntVec(str))) {}
/**
* 引数として与えられたpattern出現位置の区間を返す
*/
std::pair<int, int> findPattern(const std::string& pattern) const {
auto find = [&](const std::string& ptn) {
int end = m_suffixArray.size();
int ptn_sz = ptn.size();
auto ret = binarySearch(0, end, [&](int mid) {
int st = m_suffixArray[mid];
int sub_sz = end - st;
for(int k = 0; k < std::min(ptn_sz, sub_sz); ++k) {
if(ptn[k] < m_str[st + k]) { return true; }
if(ptn[k] > m_str[st + k]) { return false; }
}
return ptn_sz <= sub_sz;
});
return ret;
};
auto patternUpper = [&pattern]() {
auto ptn = pattern;
++* ptn.rbegin();
return ptn;
}();
auto fl = find(pattern);
auto fu = find(patternUpper);
return {fl,fu};
}
auto getSuffixArray() const {
return m_suffixArray;
}
/* output fot debug */
void debugOutput() const {
for(const auto& x : m_suffixArray) {
std::cout << x << " ";
}std::cout << std::endl;
auto end = m_str.size();
for(const auto& x : m_suffixArray) {
std::cout << m_str.substr(x, end) << std::endl;
}
}
};
class LCPArray {
const std::vector<int> m_lcpArray;
const std::vector<int> m_suffixArray;
static std::vector<int> constructLcpArray(const std::string& str) {
auto sz = str.size();
const auto suffixArray = SuffixArray(str).getSuffixArray();
auto rank = std::vector<int>(sz);
for(int i = 0; i < sz; ++i) { rank[suffixArray[i]] = i; }
auto lcpArray = std::vector<int>(sz - 1);
for(int i = 0, h = 0; i < sz; ++i) {
if(rank[i] == 0) { continue; }
int j = suffixArray[rank[i] - 1];
if(h > 0) { --h; }
for(; j + h < sz && i + h < sz; ++h) {
if(str[i + h] != str[j + h]) { break; }
}
lcpArray[rank[i] - 1] = h;
}
return lcpArray;
}
public:
LCPArray(const std::string& str) :
m_suffixArray(SuffixArray(str).getSuffixArray()),
m_lcpArray(constructLcpArray(str)) {
}
auto getLCPArray()const { return m_lcpArray; }
auto getSuffixArray()const { return m_suffixArray; }
auto getSuffixArrayIndexList()const {
std::vector<int> sail(m_suffixArray.size());
for(unsigned int i = 0; i < m_suffixArray.size(); ++i) {
sail[m_suffixArray[i]] = i;
}
return sail;
}
};
template <class SG>
class DisjointSparseTable {
using S = decltype(SG::Type());
const int m_n;
const std::vector<std::vector<SG>> m_table;
static auto accumulation(int n, const std::vector<S>& a, int l, int r) {
auto mid = (r + l) >> 1;
r = std::min(n, r);
int size = r - l;
std::vector<SG> acc; acc.reserve(size);
for(int i = l; i < r; ++i) { acc.emplace_back(a[i]); }
for(int i = mid - 2; i >= l; --i) if(i - l + 1 < size) {
acc[i - l] = acc[i - l].binaryOperation(acc[i - l + 1]);
}
for(int i = mid + 1; i < r; ++i)if(i - l - 1 >= 0) {
acc[i - l] = acc[i - l - 1].binaryOperation(acc[i - l]);
}
return acc;
}
static auto constructTable(int n, const std::vector<S>& a) {
std::vector<std::vector<SG>> table; table.reserve(std::log2(n) + 1);
table.emplace_back(a.begin(), a.end());
auto size = 1;
while(size < n) {
size <<= 1;
std::vector<SG> acc; acc.reserve(n);
for(int l = 0; l < n; l += size) for(const auto& x : accumulation(n, a, l, l + size)) {
acc.emplace_back(x);
}
table.emplace_back(acc);
}
return table;
}
static auto msb(int x) {
auto idx = 0;
while(x > 0) { ++idx; x >>= 1; }
return idx;
}
public:
DisjointSparseTable(int n, const std::vector<S>& a) :m_n(n), m_table(constructTable(n, a)) {}
auto get(int l, int r)const {
if(r < l) { throw std::runtime_error("ERROR! `l` must less than `r`"); }
l = std::max(l, 0); r = std::min(r, m_n - 1);
if(l == r) { return m_table[0][l].m_val; }
auto idx = msb(l ^ r);
return m_table[idx][l].binaryOperation(m_table[idx][r]).m_val;
}
};
template<
class S,// 要素の型
class T // 2項演算子
>
struct SemiGroup {
static inline auto Type() { return S(); }
S m_val;
SemiGroup(S val) :m_val(val) {}
SemiGroup binaryOperation(const SemiGroup& m2)const { return T()(m_val, m2.m_val); }
friend std::ostream& operator<<(std::ostream& os, const SemiGroup<S, T>& m) {
return os << m.m_val;
}
};
struct Functor { auto operator()(int a, int b)const { return std::min(a, b); } };
using SG = SemiGroup<int, Functor>;
auto solve(ll n, const std::string& s) {
auto lcp_ = LCPArray(s);
auto sa = lcp_.getSuffixArray();
auto lcpa = lcp_.getLCPArray();
auto dst = DisjointSparseTable<SG>(n - 1, lcpa);
auto i = std::find(ALL(sa), 0) - sa.begin();
auto l = n - i - 1;
auto r = binarySearch(0, i, [&](ll mid) {
if(mid == 0) { return true; }
auto k = i - mid;
auto lcp = dst.get(k, i - 1);
// dump(k, lcp, sa[k]);
if(lcp != (n - sa[k])) { return false; }
if(sa[k] >= ((n + 1) >> 1)) { return false; }
return true;
}, true);
//dump(sa, l, r, i);
//SuffixArray(s).debugOutput();
return l + r;
}
signed main() {
ll t;
cin >> t;
REP(_, t) {
ll n;
std::string s;
cin >> n >> s;
cout << solve(n, s) << endl;
}
}