QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#628523 | #7723. Hash Server | List | 0 | 0ms | 0kb | C++20 | 6.0kb | 2024-10-10 20:45:29 | 2024-10-10 20:49:22 |
answer
#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl '\n'
#define log(...) (void(0))
#endif
#define debug(x) log(" >> %s: %lld\n", #x, x)
using namespace std;
using ll = long long;
using lll = __int128;
using lf = long double;
using ull = unsigned long long;
const int n = 10;
const ll mod = 141167095653376;
int T, low[n][n][n], high[n][n];
mt19937 rng(20040129);
ll norm(ll x) {
x %= mod;
return x < 0 ? x + mod : x;
}
ll power(ll a, ll b) {
lll s = 1;
for (; b; b >>= 1, a = (lll)a * a % mod)
if (b & 1) s = (lll)s * a % mod;
return s;
}
ll encode( //
string s, //
int x = 73, //
array<int, n> a = {71, 67, 61, 59, 53, 47, 43, 41, 37, 31}, //
array<int, n> k = {29, 23, 19, 17, 13, 11, 7, 5, 3, 2} //
) {
ll res = 0;
for (int i = 0; i < n; i++) {
int c = s[i] - 'a' + 1;
res = (res + (lll)c * power(x, k[i]) % mod * (a[i] + c)) % mod;
}
return res;
}
ll s2i(string s) {
ll res = 0;
for (int i = 0; i < n; i++) {
res = (res * 26 + (s[i] - 'a'));
}
assert(0 <= res && res < mod);
return res;
}
string i2s(ll x) {
string s;
s.resize(n);
for (int i = n - 1; i >= 0; i--) {
s[i] = x % 26 + 'a';
x /= 26;
}
assert(x == 0);
return s;
}
namespace prog1 {
void solve() {
for (int i = 0; i < n; i++) { // 第几位 decoder
for (int j = 0; j < n; j++) { // 第几个数
string s;
s.resize(n);
for (int k = 0; k < n; k++) {
if (k < i) {
s[k] = low[i][j][k];
} else if (k == i) {
s[k] = j;
} else {
s[k] = high[i][k];
}
s[k] += 'a';
}
cout << s << endl;
cerr << i2s(encode(s)) << endl;
}
}
cout << "done" << endl;
}
} // namespace prog1
namespace prog2 {
vector<ll> rem;
struct atom {
int x;
ll p, q;
ll diff[n], fun[n];
ll get(int i) { return ((lll)i * p + (lll)i * i * q) % mod; }
void solve(int);
} b[n];
#define thatone (rem[i] == 85569017343074 && rem[j] == 109256991037158 && rem[k] == 8496613312874)
void atom::solve( //
int bit // 当前处理的是第几位的hasher
) {
for (int i = 0; i < n; i++) { // 第几个数
for (int j = 0; j < bit; j++) { // 第几位 (low)
diff[i] += b[j].get(low[bit][i][j] + 1);
// log("i=%d j=%d >> %d\n", i, j, low[bit][i][j] + 1);
}
diff[i] = norm(diff[i]);
}
// log("diff[%d] = ", bit);
// for (int i = 0; i < n; i++) log("%lld%c", diff[i], " \n"[i + 1 == n]);
sort(rem.begin(), rem.end());
int len = sz(rem);
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if (i == j) continue;
for (int k = 0; k < len; k++) {
if (i == k || j == k) continue;
// if (thatone) log("! i=%d j=%d k=%d\n", i, j, k);
ll C_p_q = norm(rem[i] - diff[0]);
ll p_q3 = norm((rem[j] - diff[1]) - (rem[i] - diff[0]));
ll p_q5 = norm((rem[k] - diff[2]) - (rem[j] - diff[1]));
ll q2 = norm(p_q5 - p_q3);
if (q2 % 2 == 1) continue;
for (int _ = 0; _ < 2; _++) {
if (thatone) log("!!! _=%d\n", _);
this->q = norm(q2 / 2 + _ * (mod >> 1));
this->p = norm(p_q3 - q * 3);
ll C = norm(C_p_q - p - q);
if (thatone) {
debug(C_p_q);
debug(p_q3);
debug(p_q5);
debug(q2);
debug(q);
debug(p);
debug(C);
}
bool fl = true;
if (thatone) log("rem: %lld %lld %lld\n", rem[i], rem[j], rem[k]);
for (int t = 0; t < n; t++) {
fun[t] = norm(diff[t] + C + p * (t + 1) + q * (t + 1) * (t + 1));
if (thatone) debug(fun[t]);
if (t > 2) {
auto it = lower_bound(all(rem), fun[t]);
if (it == rem.end() || *it != fun[t]) {
fl = false;
break;
}
}
}
if (fl) {
assert(fun[0] == rem[i]);
assert(fun[1] == rem[j]);
assert(fun[2] == rem[k]);
for (int t = 0; t < n; t++) {
rem.erase(lower_bound(all(rem), fun[t]));
}
log("FOUND bit=%d >> p=%lld q=%lld\n", bit, p, q);
return;
}
}
}
}
}
log("bit[%d] failed!\n", bit);
assert(false);
}
ll myencode(string s) {
ll res = 0;
for (int i = 0; i < n; i++) {
res += b[i].get(s[i] - 'a' + 1);
}
return res % mod;
}
void solve() {
int _;
cin >> _;
assert(_ == n * n);
for (int i = 0; i < n * n; i++) {
string s;
cin >> s;
rem.push_back(s2i(s));
// log("i=%d s=%s x=%lld\n", i, s.c_str(), s2i(s));
}
for (int i = 0; i < n; i++) {
b[i].solve(i);
}
for (int i = 1; i <= n * n; i++) {
string s;
cin >> s;
assert(s.length() == n);
cout << i2s(myencode(s)) << endl;
}
}
} // namespace prog2
int main() {
#ifdef memset0
freopen("H.in", "r", stdin);
// freopen("H.out", "w", stdout);
#endif
cin.tie(0)->sync_with_stdio(0);
// cout << encode("aaaaaaaaaa") << endl;
// cout << i2s(encode("aaaaaaaaaa")) << endl;
// return 0;
cin >> T;
for (int i = 0; i < n; i++) { // 第几位 decoder
for (int j = 0; j < n; j++) { // 第几个数
for (int k = 0; k < i; k++) { // 第几位的数码
low[i][j][k] = rng() % 26;
}
}
}
for (int i = 0; i < n; i++) { // 第几位 decoder
for (int k = i + 1; k < n; k++) { // 第几位的数码
high[i][k] = rng() % 26;
}
}
if (T == 1) {
prog1::solve();
} else if (T == 2) {
prog2::solve();
}
}
详细
Test #1:
score: 0
Instance #1 Time Limit Exceeded
input:
1 ndfhrzmmlq dbtusidgtk tlnputvfcu kgmsziohnu bmregaioak teaxovdyoq lgpyztanem dukimtyfvy wtkabxxcpa qdoztexdjs ptttxbxies udfaxiqglq borwqicyvy bozegnbfag auktitljge vefnyoyqre fnucuohotu rggcxcuzry hlxazgynem jbweawrale vhmlrkjnym vkzmtmacnw bhzrczyfrk yayrylktpo gopjybgmze uquulirdzi jkrqoapblu a...
output:
ahzvaqhdff bhzvaqhdff chzvaqhdff dhzvaqhdff ehzvaqhdff fhzvaqhdff ghzvaqhdff hhzvaqhdff ihzvaqhdff jhzvaqhdff gazcyylaig ybzcyylaig eczcyylaig zdzcyylaig qezcyylaig dfzcyylaig igzcyylaig rhzcyylaig pizcyylaig ujzcyylaig waacpwnpiu tcbcpwnpiu gsccpwnpiu tydcpwnpiu hxecpwnpiu vsfcpwnpiu hvgcpwnpiu hgh...
input:
2 100 vhmlrkjnym qlyffbuutu bhzrczyfrk lqcpwxefhq wscdwkluos ecuuijrrwk wtkabxxcpa cvzlhdiplm jbweawrale udcxpoulns hqqjujhmfg mucgklfkyg auktitljge myngxvuoku gtnxszwrxq mrcbgmgmto hxlcuddnqo tlnputvfcu adnbhvonau xrhcepnibg dkrnywyjdk thtmvwgmuc aihbjugisa tirwcpehqu jzunixvmwm rvwsbyrxls lgpyztan...