QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#560312 | #669. Hash | ucup-team1198# | ML | 0ms | 0kb | C++20 | 1.9kb | 2024-09-12 15:05:32 | 2024-09-12 15:05:34 |
Judging History
answer
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int MOD;
int add(int a, int b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
int sub(int a, int b) {
return a >= b ? a - b : a + MOD - b;
}
int mul(int a, int b) {
return (1ll * a * b) % MOD;
}
int B;
int get_h(string s) {
int h = 0;
for (auto ch : s) {
h = add(mul(h, B), ch - 'a' + 1);
}
return h;
}
const int MAXMOD = 1e9;
string mem[MAXMOD / 25 + 1];
int h[MAXMOD / 25 + 1];
string s;
void go(int hsh) {
if ((int)s.size() == 6) {
hsh = mul(hsh, B);
int id = hsh / 25;
if (!mem[id].empty()) {
string t = mem[id];
int h1 = h[id];
s.push_back('a');
t.push_back('a');
if (h1 > hsh) {
s.back() += (h1 - hsh);
} else {
t.back() += (hsh - h1);
}
vector<int> all;
for (int i = 0; i < 100; ++i) {
string cur;
for (int j = 0; j < 7; ++j) {
if (i & (1 << j)) {
cur += s;
cout << s;
} else {
cur += t;
cout << t;
}
}
all.push_back(get_h(cur));
cout << "\n";
}
sort(all.begin(), all.end());
assert(all[0] == all.back());
exit(0);
}
mem[id] = s;
h[id] = hsh;
return;
}
for (int i = 0; i < 26; ++i) {
s.push_back('a' + i);
int hsh1 = add(mul(hsh, B), i + 1);
go(hsh1);
s.pop_back();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> B >> MOD;
go(0);
return 0;
}
詳細信息
Test #1:
score: 0
Memory Limit Exceeded
input:
215465827 841597626
output:
aaajaaeaaajaaeaaajaaeaaajaaeaaajaaeaaajaaeaaajaae aafafjaaaajaaeaaajaaeaaajaaeaaajaaeaaajaaeaaajaae aaajaaeaafafjaaaajaaeaaajaaeaaajaaeaaajaaeaaajaae aafafjaaafafjaaaajaaeaaajaaeaaajaaeaaajaaeaaajaae aaajaaeaaajaaeaafafjaaaajaaeaaajaaeaaajaaeaaajaae aafafjaaaajaaeaafafjaaaajaaeaaajaaeaaajaaeaaajaae ...