QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#423456#7518. GCD of Pattern MatchingpandapythonerWA 1ms3804kbC++172.2kb2024-05-28 02:49:202024-05-28 02:49:20

Judging History

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

  • [2024-05-28 02:49:20]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3804kb
  • [2024-05-28 02:49:20]
  • 提交

answer

#pragma GCC optimize("Ofast,unroll-loops,fast-math")
// #pragma GCC target("avx,avx2")


#include <bits/stdc++.h>


using namespace std;


#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


const ll inf = 1e18;
mt19937 rnd(234);
const ll mod = 1e9 + 7;
typedef complex<flt> base;
const flt pi = atan2(1, 0) * 2;





int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    int t;
    cin >> t;
    for (int itr = 0; itr < t; itr += 1) {
        int m;
        string s;
        cin >> m >> s;
        string f = s;
        sort(all(f));
        f.resize(unique(all(f)) - f.begin());
        assert((int)f.size() <= m);
        int n = (int)s.size();
        vector<int> a(n);
        for (int i = 0; i < n; i += 1) {
            a[i] = lower_bound(all(f), s[i]) - f.begin();
        }
        vector<int> p(m);
        for (int i = 0; i < m; i += 1) {
            p[i] = i;
        }
        unsigned ll rs = 0;
        unsigned ll x = 0;
        shuffle(all(p), rnd);
        for (int i = 0; i < n; i += 1) {
            x = x * m + p[a[i]];
        }
        vector<unsigned ll> vals(m);
        unsigned ll pwr = 1;
        for (int i = n - 1; i >= 0; i -= 1) {
            vals[a[i]] += pwr;
            pwr *= m;
        }
        for (ll r = 0; r < 60; r += 1) {
            for (int aboba = 0; aboba < 8; aboba += 1) {
                int i = rnd() % m;
                int j = rnd() % m;
                x -= vals[i] * p[i] + vals[j] * p[j];
                swap(p[i], p[j]);
                x += vals[i] * p[i] + vals[j] * p[j];
            }
            /*
            shuffle(all(p), rnd);
            if (p[a[0]] == 0) {
                continue;
            }
            unsigned ll x = 0;
            for (int i = 0; i < m; i += 1) {
                x += vals[i] * p[i];
            }
            */
            if (rs == 0) {
                rs = x;
            } else if (x % rs != 0) {
                rs = gcd(rs, x);
            }
        }
        cout << rs << "\n";
    }
    return 0;
}

/*
1
16 abcdefghijklmnop

*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3804kb

input:

5
10 ccpcccpc
10 cpcpcp
10 cpc
4 cpccpc
4 dhcp

output:

10001
10101
1
65
3

result:

ok 5 number(s): "10001 10101 1 65 3"

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3660kb

input:

30
2 ab
3 abc
4 abcd
5 abcde
6 abcdef
7 abcdefg
8 abcdefgh
9 abcdefghi
10 abcdefghij
11 abcdefghijk
12 abcdefghijkl
13 abcdefghijklm
14 abcdefghijklmn
15 abcdefghijklmno
16 abcdefghijklmnop
16 a
16 ab
16 abc
16 abcd
16 abcde
16 abcdef
16 abcdefg
16 abcdefgh
16 abcdefghi
16 abcdefghij
16 abcdefghijk
...

output:

1
1
3
2
5
3
7
4
9
5
11
6
13
7
15
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

result:

wrong answer 1st numbers differ - expected: '2', found: '1'