QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#88848 | #3833. Kurt Gödel | SorahISA | TL | 0ms | 0kb | C++20 | 3.1kb | 2023-03-17 19:33:49 | 2023-03-17 19:33:53 |
Judging History
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 == 1) {
S.resize(L);
dfs(L, 0, S, 1);
for (auto &[val, str] : st[0]) {
if (val == res) ++cnt, ans = str;
}
}
else {
S.resize(L/2);
dfs(L/2, 0, S, 1);
st[0].swap(st[1]);
S.resize(L - L/2);
dfs(L, L/2, S, 1);
sort(ALL(st[0]));
for (auto &[val, str] : st[1]) {
int goal = fpow(val) * res % mod;
const string _min = "", _max = "a";
auto it_l = lower_bound(ALL(st[0]), pair{goal, _min});
auto it_r = lower_bound(ALL(st[0]), pair{goal, _max});
while (cnt <= 1 and it_l != it_r) {
// debug(str, (*it_l).second);
++cnt, ans = str + (*it_l).second;
it_l = next(it_l);
}
if (cnt > 1) break;
}
}
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;
}
详细
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...