QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#70700#5065. Beautiful Stringnocriz#TL 1056ms639508kbC++179.6kb2023-01-07 15:51:502023-01-07 15:51:53

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-07 15:51:53]
  • 评测
  • 测评结果:TL
  • 用时:1056ms
  • 内存:639508kb
  • [2023-01-07 15:51:50]
  • 提交

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; }

int ch[12600000][10], val[12600000], cno = 0;
int newnode(int cv, char c){
    int t = c-'0';
    if(ch[cv][t]) return ch[cv][t];
    ch[cv][t] = cno+1; cno+=1;
    memset(ch[cno],0,sizeof(ch[cno]));
    val[cno] = 0;
    return cno;
}

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]));
    }
    
    cno = 0; memset(ch[0],0,sizeof(ch[0])); val[0] = 0;

    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;
    vi C = {0};
    for(int i = n-1;i>=1;i--){
    	int cv = 0;
        for(int j=i-1;j>=0;j--){
        	cv = newnode(cv,S[j]);
            if(csu[j][i-1]){
                ans += 1ll*csu[j][i-1]*val[cv];
            }
        }
        for(auto &ct:C){
        	ct = newnode(ct, S[i]);
        	val[ct] += 1;
        }
        C.pb(0);
    }
    ps(ans);
}

int main() {
    int T;
    re(T);
    while(T--){
        solve();
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 7644kb

input:

2
114514
0000000

output:

1
3

result:

ok 2 number(s): "1 3"

Test #2:

score: 0
Accepted
time: 1056ms
memory: 639508kb

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: 14ms
memory: 11696kb

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: 14ms
memory: 11712kb

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: 0
Accepted
time: 816ms
memory: 115756kb

input:

15
111111111111111111111111111111111111111111111111111111111111121111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111211111111111111111111111111111111111111111111111...

output:

6611556286
8447635347
4351265656
8244172287
6847075843
5064323828
5818821992
5187397748
6202849391
7100699750
8826693258
9304467838
9691754783
12524687288
10378182916

result:

ok 15 numbers

Test #6:

score: 0
Accepted
time: 1026ms
memory: 128112kb

input:

15
111111111111111111111111111111111111111111111111111111121112111111111111111111111111211111112111111111111111111111111112112111111111211111111111111111121211111111111111111112121111211112112111111112111111111111111112111111111111111111111111111111111111111211111211211111111111111112211111111111111...

output:

99283290
121730268
95231372
139100190
109487920
93015077
138212377
180336129
94959502
88117283
81796472
100172151
133716692
92198870
119549081

result:

ok 15 numbers

Test #7:

score: -100
Time Limit Exceeded

input:

6
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

385321895637
278064026340
462204013200

result: