QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61102#3833. Kurt GödelNYCU_Yamada#TL 0ms0kbC++203.0kb2022-11-09 22:05:562022-11-09 22:05:59

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-11-09 22:05:59]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 0kb
  • [2022-11-09 22:05:56]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define double __float80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, greater<T>, vector<T>>;

// #define X first
// #define Y second
#define ee emplace
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)

#ifdef local
#define fastIO() void()
#define debug(...) \
    fprintf(stderr, "\u001b[33m"), \
    fprintf(stderr, "At [%s], line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), \
    fprintf(stderr, "\u001b[0m")
template <typename T> void _do(T &&_t) {cerr << _t << endl;}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif

template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

int mod;

vector<int> prime{2, 3, 5, 7, 11, 13, 17, 19};

vector<pair<int, string>> st[2];

int fpow(int base, int exp = mod-2, int ans = 1) {
    while (exp) {
        if (exp & 1) ans = ans * base % mod;
        exp >>= 1, base = base * base % mod;
    }
    return ans;
}

void dfs(int lim, int now, string &S, int val) {
    if (now == lim) {st[0].eb(val, S); return;}
    for (int i = 1; i <= 26; ++i) {
        S[now] = (char)('A' + i - 1);
        dfs(lim, now+1, S, (val = val * prime[now] % mod));
    }
}

void solve(int L, int res) {
    string S, ans;
    int cnt = 0;
    
    if (mod <= prime[L-1]) {
        if (res == 0) cout << "ambiguous" << "\n";
        else          cout << "not a word" << "\n";
        return;
    }
    
    else if (L <= 4) {
        S.resize(L);
        dfs(L, 0, S, 1);
        for (auto [val, str] : st[0]) {
            if (val == res) ++cnt, ans = str;
        }
    }
    
    else {
        S.resize(4);
        dfs(4, 0, S, 1);
        st[0].swap(st[1]);
        S.resize(L-4);
        dfs(L, 4, S, 1);
        sort(ALL(st[0]));
        
        for (auto [val, str] : st[1]) {
            auto it_l = lower_bound(ALL(st[0]), pair{fpow(val) * res % mod, ""s});
            auto it_r = lower_bound(ALL(st[0]), pair{fpow(val) * res % mod, "a"s}); /// 'a' > 'Z'
            while (it_l != it_r) {
                // debug(str, (*it_l).second);
                ++cnt, ans = str + (*it_l).second;
                it_l = next(it_l);
            }
        }
    }
    
         if (cnt == 0) cout << "not a word" << "\n";
    else if (cnt >  1) cout << "ambiguous" << "\n";
    else               cout << ans << "\n";
}

int32_t main() {
    fastIO();
    
    int l, r, p;
    while (cin >> l >> r >> p and p) mod = p, solve(l, r);
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

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:


result: