QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#423456 | #7518. GCD of Pattern Matching | pandapythoner | WA | 1ms | 3804kb | C++17 | 2.2kb | 2024-05-28 02:49:20 | 2024-05-28 02:49:20 |
Judging History
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
*/
Details
Tip: Click on the bar to expand more detailed information
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'