QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#49877#3833. Kurt Gödelckiseki#AC ✓4852ms100132kbC++202.6kb2022-09-23 19:08:082022-09-23 19:08:10

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-23 19:08:10]
  • Judged
  • Verdict: AC
  • Time: 4852ms
  • Memory: 100132kb
  • [2022-09-23 19:08:08]
  • Submitted

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;
}

詳細信息

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