QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#70698 | #5065. Beautiful String | nocriz# | TL | 1316ms | 994116kb | C++17 | 9.4kb | 2023-01-07 15:43:19 | 2023-01-07 15:47:07 |
Judging History
answer
// 苔花如米小,也学牡丹开。
// Zhikun Wang (nocriz)
// 敢问路在何方 路在脚下
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using db = long double; using str = string;
using pi = pair<int,int>; using pl = pair<ll,ll>; using pd = pair<db,db>;
using vi = vector<int>; using vb = vector<bool>; using vl = vector<ll>;
using vd = vector<db>; using vs = vector<str>;
using vpi = vector<pi>; using vpl = vector<pl>; using vpd = vector<pd>;
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>; tcT, size_t SZ> using AR = array<T,SZ>; tcT> using PR = pair<T,T>;
#define mp make_pair
#define f first
#define s second
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
tcT> int lwb(V<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); }
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define each(a,x) for (auto& a: x)
const int MOD = 998244353;
const ll INF = 1e18; // not too close to LLONG_MAX
const db PI = acos((db)-1);
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0,1,0,-1}; // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr int bits(int x) { return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x))
constexpr int p2(int x) { return 1<<x; }
constexpr int msk2(int x) { return p2(x)-1; }
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
tcT> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
tcT> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
tcTU> T fstTrue(T lo, T hi, U f) { hi ++; assert(lo <= hi); while (lo < hi) { T mid = lo+(hi-lo)/2; f(mid) ? hi = mid : lo = mid+1; } return lo; }
tcTU> T lstTrue(T lo, T hi, U f) { lo --; assert(lo <= hi); while (lo < hi) { T mid = lo+(hi-lo+1)/2; f(mid) ? lo = mid : hi = mid-1; } return lo; }
tcT> void remDup(vector<T>& v) { sort(all(v)); v.erase(unique(all(v)),end(v)); }
tcTU> void erase(T& t, const U& u) { auto it = t.find(u); assert(it != end(t)); t.erase(it); }
#define tcTUU tcT, class ...U
inline namespace Helpers { tcT, class = void> struct is_iterable : false_type {}; tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>())) > > : true_type {}; tcT> constexpr bool is_iterable_v = is_iterable<T>::value; tcT, class = void> struct is_readable : false_type {}; tcT> struct is_readable<T, typename std::enable_if_t< is_same_v<decltype(cin >> declval<T&>()), istream&> > > : true_type {}; tcT> constexpr bool is_readable_v = is_readable<T>::value; tcT, class = void> struct is_printable : false_type {}; tcT> struct is_printable<T, typename std::enable_if_t< is_same_v<decltype(cout << declval<T>()), ostream&> > > : true_type {}; tcT> constexpr bool is_printable_v = is_printable<T>::value;}
inline namespace Input { tcT> constexpr bool needs_input_v = !is_readable_v<T> && is_iterable_v<T>; tcTUU> void re(T& t, U&... u); tcTU> void re(pair<T,U>& p); tcT> typename enable_if<is_readable_v<T>,void>::type re(T& x) { cin >> x; } tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; } tcT> typename enable_if<needs_input_v<T>,void>::type re(T& i); tcTU> void re(pair<T,U>& p) { re(p.f,p.s); } tcT> typename enable_if<needs_input_v<T>,void>::type re(T& i) { each(x,i) re(x); } tcTUU> void re(T& t, U&... u) { re(t); re(u...); }}
inline namespace ToString { tcT> constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>; tcT> typename enable_if<is_printable_v<T>,str>::type ts(T v) { stringstream ss; ss << fixed << setprecision(15) << v; return ss.str(); } tcT> str bit_vec(T t) { str res = "{"; F0R(i,sz(t)) res += ts(t[i]); res += "}"; return res; } str ts(V<bool> v) { return bit_vec(v); } template<size_t SZ> str ts(bitset<SZ> b) { return bit_vec(b); } tcTU> str ts(pair<T,U> p); tcT> typename enable_if<needs_output_v<T>,str>::type ts(T v); tcTU> str ts(pair<T,U> p) { return "("+ts(p.f)+", "+ts(p.s)+")"; } tcT> typename enable_if<is_iterable_v<T>,str>::type ts_sep(T v, str sep) { bool fst = 1; str res = ""; for (const auto& x: v) { if (!fst) res += sep; fst = 0; res += ts(x); } return res; } tcT> typename enable_if<needs_output_v<T>,str>::type ts(T v) { return "{"+ts_sep(v,", ")+"}"; } template<int, class T> typename enable_if<!needs_output_v<T>,vs>::type ts_lev(const T& v) { return {ts(v)}; } template<int lev, class T> typename enable_if<needs_output_v<T>,vs>::type ts_lev(const T& v) { if (lev == 0 || !sz(v)) return {ts(v)}; vs res; for (const auto& t: v) { if (sz(res)) res.bk += ","; vs tmp = ts_lev<lev-1>(t); res.ins(end(res),all(tmp)); } F0R(i,sz(res)) { str bef = " "; if (i == 0) bef = "{"; res[i] = bef+res[i]; } res.bk += "}"; return res; } }
inline namespace Output { template<class T> void pr_sep(ostream& os, str, const T& t) { os << ts(t); } template<class T, class... U> void pr_sep(ostream& os, str sep, const T& t, const U&... u) {pr_sep(os,sep,t); os << sep; pr_sep(os,sep,u...); } template<class ...T> void pr(const T&... t) { pr_sep(cout,"",t...); } void ps() { cout << "\n"; } template<class ...T> void ps(const T&... t) { pr_sep(cout," ",t...); ps(); } template<class ...T> void dbg_out(const T&... t) { pr_sep(cerr," | ",t...); cerr << endl; }void loc_info(int line, str names) { cerr << "Line(" << line << ") -> [" << names << "]: "; } template<int lev, class T> void dbgl_out(const T& t) { cerr << "\n\n" << ts_sep(ts_lev<lev>(t),"\n") << "\n" << endl; } }
#ifdef LOCAL
#define dbg(...) loc_info(__LINE__,#__VA_ARGS__), dbg_out(__VA_ARGS__)
#define dbgl(lev,x) loc_info(__LINE__,#x), dbgl_out<lev>(x)
#else
#define dbg(...) 0
#define dbgl(lev,x) 0
#endif
void decrement() {} // subtract one from each
tcTUU> void decrement(T& t, U&... u) { --t; decrement(u...); }
#define ints(...) int __VA_ARGS__; re(__VA_ARGS__);
#define int1(...) ints(__VA_ARGS__); decrement(__VA_ARGS__);
using H = AR<int,2>; // bases not too close to ends
H makeH(char c) { return {c,c}; }
uniform_int_distribution<int> BDIST(0.1*MOD,0.9*MOD);
const H base{BDIST(rng),BDIST(rng)};
/// const T ibase = {(int)inv(mi(base[0])),(int)inv(mi(base[1]))};
H operator+(H l, H r) {
F0R(i,2) if ((l[i] += r[i]) >= MOD) l[i] -= MOD;
return l; }
H operator-(H l, H r) {
F0R(i,2) if ((l[i] -= r[i]) < 0) l[i] += MOD;
return l; }
H operator*(H l, H r) {
F0R(i,2) l[i] = (ll)l[i]*r[i]%MOD;
return l; }
/// H& operator+=(H& l, H r) { return l = l+r; }
/// H& operator-=(H& l, H r) { return l = l-r; }
/// H& operator*=(H& l, H r) { return l = l*r; }
V<H> pows{{1,1}};
struct HashRange {
str S; vector<H> cum{{}};
void add(char c) { S += c; cum.pb(base*cum.bk+makeH(c)); }
void add(str s) { each(c,s) add(c); }
void extend(int len) { while (sz(pows) <= len) pows.pb(base*pows.bk); }
ll hash(int l, int r) { int len = r+1-l; extend(len);
H ret = cum[r+1]-pows[len]*cum[l]; return 1ll*ret[0]*MOD+ret[1];}
/**int lcp(HashRange& b) { return first_true([&](int x) {
return cum[x] != b.cum[x]; },0,min(sz(S),sz(b.S)))-1; }*/
};
/// HashRange HR; HR.add("ababab"); F0R(i,6) FOR(j,i,6) ps(i,j,HR.hash(i,j));
int csu[5050][5050];
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
struct chash { /// use most bits rather than just the lowest ones
const uint64_t C = ll(2e18*PI)+71; // large odd number
const int RANDOM = rng();
ll operator()(ll x) const { /// https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
return __builtin_bswap64((x^RANDOM)*C); }
};
template<class K,class V> using um = unordered_map<K,V,chash>;
template<class K,class V> using ht = gp_hash_table<K,V,chash>;
template<class K,class V> V get(ht<K,V>& u, K x) {
auto it = u.find(x); return it == end(u) ? 0 : it->s; }
char lvis[71000000];
int cnt[71000000];
ll v[71000000];
char cc = 0;
int get(ll va){
int cv = va%70000823;
while(lvis[cv] == cc && v[cv]!=va){
cv+=1;
}
if(v[cv] != va || lvis[cv] != cc) return 0;
return cnt[cv];
}
void ads(ll va){
int cv = va%70000823;
while(lvis[cv] == cc && v[cv]!=va){
cv+=1;
}
if(lvis[cv]!= cc){
v[cv] = va; lvis[cv] = cc;
cnt[cv] = 0;
}
cnt[cv]+=1;
}
void solve(){
HashRange HR;
str S;
re(S);
int n = sz(S);
HR.add(S);
for(int i=0;i<n;i++){
memset(csu[i], 0, sizeof(csu[i]));
}
for(int i=0;i<n;i++){
for(int j=1;i+j+j<n;j++){
if(HR.hash(i,i+j-1) == HR.hash(i+j,i+j+j-1)){
csu[i+j][i+j+j]+=1;
}
}
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
csu[i][j]+=csu[i][j-1];
}
}
ll ans = 0;
for(int i = n-1;i>=1;i--){
for(int j=i-1;j>=0;j--){
if(csu[j][i-1]){
ans += 1ll*csu[j][i-1]*get(HR.hash(j,i-1));
}
}
for(int j=i;j<n;j++)ads(HR.hash(i,j));
}
ps(ans);
}
int main() {
int T;
re(T);
while(T--){
cc+=1;
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 79252kb
input:
2 114514 0000000
output:
1 3
result:
ok 2 number(s): "1 3"
Test #2:
score: 0
Accepted
time: 1316ms
memory: 994116kb
input:
11 79380 2483905227 37902399703986576270 39991723655814713848046032694137883815354365954917 5541883522667841718787744915558298207485830622522715211018760095628594390563630840464643840093757297 56530485554219245862513973750218715585679416120445975390556326891488719311495909340757506478400624741858999...
output:
0 0 0 2 4 20 119 113 1086 2128 15166
result:
ok 11 numbers
Test #3:
score: 0
Accepted
time: 89ms
memory: 900464kb
input:
50 11111111111111111111111111111111111111121111111111111111111111111111111111111112111111111121111111111211111121211121111111111111111111111111111211121111111111111111111111111111111111111111111111111112 111111111111111111111111111111111111111111111121111121111111111111111111111111111111111111111111...
output:
779344 799116 716078 723215 1197647 403357 652134 625671 414294 942493 390998 793444 612061 507395 473508 836065 461623 374925 539333 592574 676408 610940 463761 490048 995917 595830 424894 332669 596834 655095 521489 1032050 697420 752056 406316 360973 1180943 948628 478572 1026603 711224 429752 49...
result:
ok 50 numbers
Test #4:
score: 0
Accepted
time: 103ms
memory: 899256kb
input:
50 11211121122222111222111111222112111221112111121112221111111121211111212211212122112212221221112112221221112211211112121222112221211122112211112111112112211121222111222212211121111111112111112121111122 112112121211212111212221221222211211121212221111112122121211112221221121121112111221211112122121...
output:
7499 6375 7041 7889 6622 6804 8695 8795 7018 8387 8910 8019 8223 8820 7324 7144 8035 9941 7073 7373 7427 7280 6946 8204 7931 6769 7050 9268 7682 8232 7797 7356 7012 8967 7469 6869 11728 6562 7604 8840 7885 8658 7006 8156 10694 6716 6121 7499 7456 7981
result:
ok 50 numbers
Test #5:
score: -100
Time Limit Exceeded
input:
15 111111111111111111111111111111111111111111111111111111111111121111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111211111111111111111111111111111111111111111111111...
output:
6611556286 8447635347 4351265656 8244172287 6847075843 5064323828 5818821992 5187397748 6202849391 7100699750 8826693258 9304467838 9691754783