QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#710935#9522. A Simple String Problemucup-team3519AC ✓1970ms14832kbC++174.0kb2024-11-04 23:17:372024-11-10 22:38:16

Judging History

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

  • [2024-11-10 22:38:16]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:1970ms
  • 内存:14832kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:49:57]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1952ms
  • 内存:14960kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-11-04 23:17:38]
  • 评测
  • 测评结果:100
  • 用时:1990ms
  • 内存:14904kb
  • [2024-11-04 23:17:37]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
#define fi first
#define se second 
#define V vector
#define pb push_back
typedef long long LL;

const LL mod = 444445555566666677;
const LL base = 2333;
const int N = 1e6 + 20;

typedef uint64_t ull;
struct H {
	ull x; H(ull x=0) : x(x) {}
	H operator+(H o) { return x + o.x + (x + o.x < x); }
	H operator-(H o) { return *this + ~o.x; }
	H operator*(H o) { auto m = (__uint128_t)x * o.x;
		return H((ull)m) + (ull)(m >> 64); }
	ull get() const { return x + !~x; }
	bool operator==(H o) const { return get() == o.get(); }
	bool operator<(H o) const { return get() < o.get(); }
};

H pbs[N];
H mul(H a, H b) {
    return a * b;
}

int deal(int n, string a, string b, int prev_ans) {
    int ans = prev_ans;
    V<H> prea(n + 1);
    V<H> preb(n + 1);
    for(int i = 1; i <= n; i++) {
        prea[i] = mul(prea[i - 1], base) + a[i];
        preb[i] = mul(preb[i - 1], base) + b[i];
    }
    auto hasha = [&](int l, int r) -> H {
        assert(r >= l);
        return prea[r] - mul(prea[l - 1], pbs[r - l + 1]);
    };
    auto hashb = [&](int l, int r) -> H {
        assert(r >= l);
        return preb[r] - mul(preb[l - 1], pbs[r - l + 1]);
    };
    auto is_1 = [&](int l, int r, int k) -> bool {
        assert(r >= l);
        if(r + k > n) return 0;
        return hasha(l, r) == hasha(l + k, r + k);
    };
    auto is_2 = [&](int l, int r, int k) -> bool {
        assert(r >= l);
        if(r + k - 1 > n) return 0;
        return hasha(l, r) == hashb(l + k - 1, r + k - 1);
    };
    for(int k = n; k >= 1; k--) {
        // if(ans >= k * 2) break;
        for(int j = k; j <= n; j += k) {
            if(is_1(j, j, k)) {
                int l = 0, r = j;
                while(l != r - 1) {
                    int mid = l + r >> 1;
                    if(is_1(mid, j, k)) r = mid;
                    else l = mid;
                }
                int L1 = r;

                l = j, r = n + 1;
                while(l != r - 1) {
                    int mid = l + r >> 1;
                    if(is_1(j, mid, k)) l = mid;
                    else r = mid;
                }
                int R1 = l;

                //1 -> 2? 

                l = R1, r = n + 1;
                while(l != r - 1) {
                    int mid = l + r >> 1;
                    if(is_2(R1 + 1, mid, k)) l = mid;
                    else r = mid;
                }

                int R2 = l;

                if(R2 - L1 + 1 >= k) {
                    ans = max(ans, 2 * k);
                }
            }
            if(is_2(j, j, k)) {
                int l = 0, r = j;
                while(l != r - 1) {
                    int mid = l + r >> 1;
                    if(is_2(mid, j, k)) r = mid;
                    else l = mid;
                }
                int L2 = r;

                l = j, r = n + 1;
                while(l != r - 1) {
                    int mid = l + r >> 1;
                    if(is_2(j, mid, k)) l = mid;
                    else r = mid;
                }
                int R2 = l;

                //1 -> 2? 

                l = 0, r = L2;
                while(l != r - 1) {
                    int mid = l + r >> 1;
                    if(is_1(mid, L2 - 1, k)) r = mid;
                    else l = mid;
                }

                int L1 = r;

                if(R2 - L1 + 1 >= k) {
                    ans = max(ans, 2 * k);
                }

            }
        }
    }
    return ans;
}   
void solve() {
    int n; cin >> n;
    string a, b; cin >> a >> b;
    a = " " + a, b = " " + b;
    int ans = deal(n, a, b, 0);
    reverse(a.begin() + 1, a.end());
    reverse(b.begin() + 1, b.end());
    ans = max(ans, deal(n, b, a, ans));
    cout << ans << endl;
}
int main() {
    pbs[0] = 1;
    for(int i = 1; i < N; i++) pbs[i] = mul(base, pbs[i - 1]);
    ios::sync_with_stdio(0), cin.tie(0);
    // int t; cin >> t;
    // while(t--) 
    solve();
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 11384kb

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 4ms
memory: 11336kb

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

score: 0
Accepted
time: 4ms
memory: 11316kb

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 4ms
memory: 11340kb

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

score: 0
Accepted
time: 4ms
memory: 11436kb

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 4ms
memory: 11328kb

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 227ms
memory: 14760kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 219ms
memory: 14680kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 231ms
memory: 14664kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 1138ms
memory: 14756kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 1947ms
memory: 14740kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 1970ms
memory: 14832kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 229ms
memory: 14680kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

score: 0
Accepted
time: 4ms
memory: 11388kb

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

score: 0
Accepted
time: 4ms
memory: 11556kb

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

score: 0
Accepted
time: 0ms
memory: 11436kb

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

score: 0
Accepted
time: 0ms
memory: 11324kb

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

score: 0
Accepted
time: 4ms
memory: 11304kb

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

score: 0
Accepted
time: 4ms
memory: 11384kb

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

score: 0
Accepted
time: 4ms
memory: 11332kb

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

score: 0
Accepted
time: 4ms
memory: 11396kb

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed