QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#49877 | #3833. Kurt Gödel | ckiseki# | AC ✓ | 4852ms | 100132kb | C++20 | 2.6kb | 2022-09-23 19:08:08 | 2022-09-23 19:08:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int prs[] = {2, 3, 5, 7, 11, 13, 17, 19};
int inv[20];
int main() {
int l, r, p;
while (cin >> l >> r >> p, l || r || p) {
bool found = false;
for (int i = 0; i < l; i++) {
if (prs[i] == p) {
found = true;
}
}
if (found) {
if (r == 0) {
cout << "ambiguous\n";
} else {
cout << "not a word\n";
}
cerr << "here\n";
continue;
}
inv[1] = 1;
for (int i = 2; i < 20; i++) {
inv[i] = 1LL * inv[p % i] * (p - p / i) % p;
}
string seq(l, '\0');
const auto dfs = [&](auto self, const auto &f, auto &mp, int l, int r, int prod) -> void {
if (l == r) {
mp[prod].push_back(seq);
return;
}
const int x = f(l);
for (int j = 1; j <= 26; j++) {
prod = 1LL * prod * x % p;
seq[l] = char('A' + j - 1);
self(self, f, mp, l+1, r, prod);
seq[l] = '\0';
}
};
unordered_map<int, vector<string>> A, B;
dfs(dfs, [](int x) { return prs[x]; }, A, 0, l/2, 1);
dfs(dfs, [](int x) { return inv[prs[x]]; }, B, l/2, l, 1);
// for (auto [a, b]: A) {
// cerr << a << ':'; for (auto v: b) cerr << v.substr(0, l/2) << endl;
// }
// cerr << "---\n";
// for (auto [a, b]: B) {
// cerr << a << ':'; for (auto v: b) cerr << v.substr(l/2, l) << endl;
// }
using ll = int64_t;
string word(l, '\0');
int64_t cnt = 0;
for (const auto &[x, k]: B) {
if (auto it = A.find(1LL * r * x % p); it != A.end()) {
ll sz = ll(k.size()) * ll(it->second.size());
cnt += sz;
if (sz) {
auto &b = k[0];
auto &a = it->second[0];
for (int j = 0; j < l; j++)
if (j < l/2)
word[j] = a[j];
else
word[j] = b[j];
// cerr << "here\n";
}
}
}
if (cnt == 0) {
cout << "not a word\n";
} else if (cnt == 1) {
// for (int j = 0; j < l; j++)
// cerr << int(word[j]) << ' ';
// cerr << endl;
cout << word << '\n';
} else {
cout << "ambiguous\n";
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4852ms
memory: 100132kb
input:
1 3 7 2 0 7 3 1 101 4 0 2 5 9 11 6 0 13 7 0 5 8 1 5 7 1 709798799 7 1 679312619 8 1990201918 1990201919 2 947262865 1501617263 1 2 1628974967 5 712922736 1293506503 6 1300135140 2023929143 8 1098466532 1961982329 7 694264934 1791849959 4 1029016974 1262011019 6 477140369 1798468619 3 701451159 17590...
output:
not a word not a word ambiguous ambiguous not a word ambiguous ambiguous not a word QPEVPZY not a word not a word IN A GODEL NUMBER ambiguous ambiguous EACH SYMBOL AND FORMULA ambiguous ambiguous CALLED ambiguous ambiguous ambiguous COW ambiguous not a word
result:
ok 30 lines