QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#764797	#9522. A Simple String Problem	xhytom	AC ✓	984ms	199652kb	C++23	6.9kb	2024-11-20 10:43:08	2024-11-20 10:43:17

Judging History

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

[2024-11-20 10:43:17]
评测

测评结果：AC
用时：984ms
内存：199652kb

查看

[2024-11-20 10:43:08]
提交

answer

/*
 
_/      _/    _/      _/    _/      _/   _/_/_/_/_/     _/_/       _/      _/ 
 _/    _/     _/      _/     _/    _/        _/       _/    _/     _/      _/            
  _/  _/      _/      _/      _/  _/         _/      _/      _/    _/_/  _/_/         
   _/_/       _/_/_/_/_/        _/           _/      _/      _/    _/  _/  _/          
  _/  _/      _/      _/        _/           _/      _/      _/    _/      _/          
 _/    _/     _/      _/        _/           _/       _/    _/     _/      _/          
_/      _/    _/      _/        _/           _/         _/_/       _/      _/       
 
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
using i64 = long long;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define multi int _;cin>>_;while(_--)
#define int long long
#define pb push_back
#define eb emplace_back
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}
mt19937_64 mrand(chrono::steady_clock().now().time_since_epoch().count());
int rnd(int l,int r){ return mrand() % (r - l + 1) + l;}
#ifdef localfreopen
#define debug(x) cerr << #x << " = " << (x) << endl;
void test() {cerr << "\n";}
template<typename T, typename... Args> 
void test(T x, Args... args) {cerr << x << " ";test(args...);}
#else
#define debug //
#define test //
#endif
const ll MOD = 998244353;
// const ll MOD = 1e9+7;
ll ksm(ll x,ll y){ll ans=1;x%=MOD;while(y){if(y&1)ans=ans*x%MOD;x=x*x%MOD,y/=2;}return ans;}

const int P1 = 972152273, base1 = 809;
const int P2 = 905563261, base2 = 919;
const ll N = 200005;
//head

struct SA{
    vector<int> sa, rk, oldrk, id, key1, cnt, ht;
    vector<vector<int>> st;
    int i, m = 127, p, w;
    bool cmp(int x, int y, int w) {
        return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
    }// key1[i] = rk[id[i]]（作为基数排序的第一关键字数组）
    int n;
    SA(string s)
    {
        n = s.size() - 1;
        oldrk.resize(2 * n + 5);
        sa.resize(n + 2);
        rk.resize(n + 2);
        id.resize(n + 2);
        key1.resize(n + 2);
        cnt.resize(max(n + 5, 130ll));
        for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
        for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
        for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;
        for (w = 1;; w <<= 1, m = p) {  // m=p 就是优化计数排序值域
            for (p = 0, i = n; i > n - w; --i) id[++p] = i;
            for (i = 1; i <= n; ++i)
                if (sa[i] > w) id[++p] = sa[i] - w;
            fill(cnt.begin(), cnt.end(), 0);
            for (i = 1; i <= n; ++i) ++cnt[key1[i] = rk[id[i]]];
            // 注意这里px[i] != i，因为rk没有更新，是上一轮的排名数组
    
            for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
            for (i = n; i >= 1; --i) sa[cnt[key1[i]]--] = id[i];
            for(int i = 1 ; i <= n ; i++)
            {
                oldrk[i] = rk[i];
            }
            for (p = 0, i = 1; i <= n; ++i)
                rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
            if (p == n) {
                break;
            }
        }
        // height数组构建
        ht.resize(n + 2);
        int k = 0;
        for(int i = 1 ; i <= n ; i++ )
        {
            k = max(k - 1, 0ll);
            if(rk[i] == 1) continue;
            int j = sa[rk[i] - 1];
            while(s[i + k] == s[j + k]) k++;
            ht[rk[i]] = k;
        }

        // LCPst表构建
        st.resize(24);
        st[0].resize(n + 5); 
        for(int i = 1 ; i <= n ; i++ )
        {
            st[0][i] = ht[i];
        }
        for(int j = 1 ; j <= 22 ; j++ )
        {
            st[j].resize(n + 5);
            for(int i = 1 ; i + (1 << j) - 1 <= n ; i++ )
            {
                st[j][i] = min(st[j - 1][i], st[j - 1][i + (1ll << j - 1)]);
            }
        }
        

    } 
    int LCP(int u, int v)
    {
        if(u == v) return n - u + 1;
        if(rk[u] > rk[v]) swap(u, v);
        int l = rk[u] + 1, r = rk[v];
        int len = __lg(r - l + 1);
        return min(st[len][l], st[len][r - (1 << len) + 1]);
    }
};

signed main()
{  
#ifdef localfreopen
    // freopen("1.in","r",stdin);
#endif
    fastio
    std::cout << std::fixed << std::setprecision(10);
    
    int n;
    std::cin >> n;
    
    std::string s, t;
    std::cin >> s >> t;
    auto revs = s, revt = t;
    std::reverse(revs.begin(), revs.end());
    std::reverse(revt.begin(), revt.end());
    
    std::string str = ' ' + s + '#' + t + '@' + revs + '&' + revt + '%';
    SA sa(str);
	auto get = [&](int x, int y) {
		return sa.LCP(x, y);
	};
    auto sl = [&](int x) {
    	return 3 * n + 3 - x;
    };
    auto tl = [&](int y) {
    	return 4 * n + 4 - y;
    };
    auto sr = [&](int x) {
    	return x;
    };
    auto tr = [&](int y) {
    	return n + 1 + y;
    };
    
    
    int ans = 0;
    
    for (int d = n / 2 + 1; d >= 1; d--) {
    	for (int l = 1, r = d; r <= n; l += d, r += d) {
    		int pre = get(tl(l - 1), tl(r));
    		int bac = get(tr(l), tr(r + 1));
    		int sum = pre + bac;
    		int tmp = get(sl(l - pre), tl(r - pre));
    		sum += tmp;
    		// test(l, r, sum, tmp);
    		if (sum >= d) {
    			ans = std::max(ans, d * 2);
    		}
    	}
		for (int l = d, r = l + d - 1; r <= n; l += d, r += d) {
    		int pre = get(tl(l - 1), tl(r));
    		int bac = get(tr(l), tr(r + 1));
    		int sum = pre + bac;
    		int tmp = get(sl(l - pre), tl(r - pre));
    		sum += tmp;
    		// test(l, r, sum, tmp, "!", l - pre, r - pre, get(sl(l - pre), tl(r - pre)), sl(l - pre), tl(r - pre));
    		if (sum >= d) {
    			ans = std::max(ans, d * 2);
    		}
    	}
    }
    
	for (int d = n / 2 + 1; d >= 1; d--) {
    	for (int l = 1, r = d; r <= n; l += d, r += d) {
    		int pre = get(sl(l - 1), sl(r));
    		int bac = get(sr(l), sr(r + 1));
    		int sum = pre + bac;
    		int tmp = get(sr(l + bac), tr(r + bac));
    		sum += tmp;
    		// test(l, r, sum, tmp);
    		if (sum >= d) {
    			ans = std::max(ans, d * 2);
    		}
    	}
		for (int l = d, r = l + d - 1; r <= n; l += d, r += d) {
    		int pre = get(sl(l - 1), sl(r));
    		int bac = get(sr(l), sr(r + 1));
    		int sum = pre + bac;
    		int tmp = get(sr(l + bac), tr(r + bac));
    		sum += tmp;
    		// test(pre, bac);
    		// test(l, r, sum, tmp);
    		if (sum >= d) {
    			ans = std::max(ans, d * 2);
    		}
    	}
    }

	for (int d = n / 2 + 3; d >= 2; d--) {
    	for (int l = 1, r = d - 1; r <= n; l += d - 1, r += d - 1) {
    		int pre = get(sl(l - 1), tl(r));
    		int bac = get(sr(l), tr(r + 1));
    		int sum = pre + bac;
    		// test(l, r, sum);
    		if (sum >= d) {
    			ans = std::max(ans, d * 2);
    		}
    	}
    }
    std::cout << ans << "\n";
    
    
    return 0;
}

Source code, Language: C++23

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3620kb

input:

5
abcab
acabc

output:

result:

ok single line: '6'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3640kb

input:

6
babbaa
babaaa

output:

result:

ok single line: '6'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3860kb

input:

2
ne
fu

output:

result:

ok single line: '0'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3832kb

input:

6
baabba
baabab

output:

result:

ok single line: '4'

Test #5:

score: 0

Accepted

time: 0ms

memory: 3796kb

input:

6
aaabba
aabbba

output:

result:

ok single line: '2'

Test #6:

score: 0

Accepted

time: 0ms

memory: 3580kb

input:

6
abaabb
bbbaba

output:

result:

ok single line: '4'

Test #7:

score: 0

Accepted

time: 984ms

memory: 199292kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

result:

ok single line: '200000'

Test #8:

score: 0

Accepted

time: 926ms

memory: 199652kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

result:

ok single line: '200000'

Test #9:

score: 0

Accepted

time: 949ms

memory: 199392kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

result:

ok single line: '114514'

Test #10:

score: 0

Accepted

time: 760ms

memory: 199352kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

result:

ok single line: '0'

Test #11:

score: 0

Accepted

time: 727ms

memory: 199416kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

result:

ok single line: '150050'

Test #12:

score: 0

Accepted

time: 880ms

memory: 199588kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

result:

ok single line: '131072'

Test #13:

score: 0

Accepted

time: 693ms

memory: 199376kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

result:

ok single line: '8'

Test #14:

score: 0

Accepted

time: 0ms

memory: 3576kb

input:

10
aaabaabaaa
aabbbaaaba

output:

result:

ok single line: '6'

Test #15:

score: 0

Accepted

time: 0ms

memory: 3684kb

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

result:

ok single line: '10'

Test #16:

score: 0

Accepted

time: 0ms

memory: 3888kb

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

result:

ok single line: '8'

Test #17:

score: 0

Accepted

time: 0ms

memory: 3588kb

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

result:

ok single line: '8'

Test #18:

score: 0

Accepted

time: 0ms

memory: 3676kb

input:

5
aabba
baaba

output:

result:

ok single line: '6'

Test #19:

score: 0

Accepted

time: 0ms

memory: 3796kb

input:

1
a
a

output:

result:

ok single line: '2'

Test #20:

score: 0

Accepted

time: 0ms

memory: 3964kb

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

result:

ok single line: '20'

Test #21:

score: 0

Accepted

time: 0ms

memory: 3596kb

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

result:

ok single line: '18'

Extra Test:

score: 0

Extra Test Passed