QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #729600 | #2519. Number with Bachelors | ucup-team5226# | RE | 0ms | 3632kb | C++20 | 6.9kb | 2024-11-09 17:27:32 | 2024-11-09 17:27:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using sl = set<ll>;
#define ov4(a, b, c, d, name, ...) name
#define rep3(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define all(v) v.begin(), v.end()
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vc<vc<T>>;
void solve() {
char c;
ll t;
cin >> c >> t;
auto get = [](char c) {
if ('0' <= c and c <= '9') return c - '0';
return c - 'a' + 10;
};
auto get2 = [&](ll x) {
if (x < 10) return '0' + x;
return 'a' + x - 10;
};
vc<ll> valsd = {1, 9};
for (int i = 9; i >= 1; i--) valsd.push_back(valsd.back() * i);
auto sumd = valsd;
rep(i, 1, valsd.size()) sumd[i] += sumd[i - 1];
vc<ll> valsh = {1, 15};
for (int i = 15; i >= 1; i--) valsd.push_back(valsd.back() * i);
auto sumh = valsh;
rep(i, 1, valsh.size()) sumh[i] += sumh[i - 1];
vc<ll> fac(17, 1);
rep(i, 1, 17) fac[i] = fac[i - 1] * i;
auto nPr = [&](ll n, ll r) { return fac[n] / fac[n - r]; };
if (c == 'd') {
if (t == 0) {
auto f = [&](ll n) -> ll {
if (n < 0) return 0;
string s = to_string(n);
ll ns = s.size();
ll res = 0;
vvc<ll> dp(ns + 1, vc<ll>(2));
dp[1][1] = 1;
dp[1][0] = s[0] - '0' - 1;
set<ll> st;
st.insert(s[0] - '0');
rep(i, 2, ns + 1) {
ll val = s[i - 1] - '0';
dp[i][0] += dp[i - 1][0] * (11 - i);
if (!st.count(val)) dp[i][1] = dp[i - 1][1];
st.insert(val);
ll r = val;
rep(j, val) if (st.count(val)) r--;
dp[i][0] += dp[i - 1][1] * r;
dp[i][0] += 9;
}
return 1 + dp[ns][0] + dp[ns][1];
};
ll l, r;
cin >> l >> r;
cout << f(r) - f(l - 1) << endl;
} else {
ll i;
cin >> i;
ll d = -1;
rep(j, sumd.size()) {
ll l = 0, r = sumd[j];
if (j) l = sumd[j - 1];
if (l < i and i <= r) {
d = j;
break;
}
}
if (d == -1) {
cout << "-" << endl;
return;
}
if (d == 0) {
cout << 0 << endl;
return;
}
if (d == 1) {
cout << i - 1 << endl;
return;
}
i -= sumd[d - 1] - 1;
string res;
ll val = i / nPr(9, d - 1) + 1;
vc<ll> ban(10);
ban[val] = 1;
res +=
i %= nPr(9, d - 1);
rep(j, 1, d) {
ll cnt = 0, idx = -1;
ll num = i / nPr(10 - j, d - 1 - j) + 1;
rep(k, 10) {
if (!ban[k]) cnt++;
if (cnt == num) {
idx = k;
break;
}
}
res += get2(idx);
ban[idx] = true;
i %= nPr(10 - j, d - 1 - j);
}
}
} else {
if (t == 0) {
auto f = [&](string s) -> ll {
ll ns = s.size();
ll res = 0;
vvc<ll> dp(ns + 1, vc<ll>(2));
dp[1][1] = 1;
dp[1][0] = get(s[0]);
set<ll> st;
st.insert(get(s[0]));
rep(i, 2, ns + 1) {
ll val = get(s[i - 1]);
dp[i][0] += dp[i - 1][0] * (17 - i);
if (!st.count(val)) dp[i][1] = dp[i - 1][1];
st.insert(val);
ll r = val;
rep(j, val) if (st.count(val)) r--;
dp[i][0] += dp[i - 1][1] * r;
dp[i][0] += 15;
}
return 1 + dp[ns][0] + dp[ns][1];
};
string L, R;
cin >> L >> R;
auto g = [&](string s) {
ll res = 0;
for (auto S : s) {
res *= 16;
res += get(S);
}
return res;
};
auto h = [&](ll x) {
if (x == 0) return to_string(x);
string res;
while (x) {
res += get2(x % 16);
x /= 16;
}
reverse(res.begin(), res.end());
return res;
};
ll res = f(R);
if (L != "0") res -= f(h(g(L) - 1));
cout << h(res) << endl;
} else {
string s;
cin >> s;
auto g = [&](string s) {
ll res = 0;
for (auto S : s) {
res *= 16;
res += get(S);
}
return res;
};
ll i = g(s);
ll d = -1;
rep(j, sumh.size()) {
ll l = 0, r = sumh[j];
if (j) l = sumh[j - 1];
if (l < i and i <= r) {
d = j;
break;
}
}
if (d == -1) {
cout << "-" << endl;
return;
}
if (d == 0) {
cout << 0 << endl;
return;
}
if (d == 1) {
cout << (char)get2(i - 1) << endl;
return;
}
i -= sumh[d - 1] - 1;
string res;
ll val = i / nPr(15, d - 1) + 1;
vc<ll> ban(16);
ban[val] = 1;
res +=
i %= nPr(15, d - 1);
rep(j, 1, d) {
ll cnt = 0, idx = -1;
ll num = i / nPr(16 - j, d - 1 - j) + 1;
rep(k, 16) {
if (!ban[k]) cnt++;
if (cnt == num) {
idx = k;
break;
}
}
res += get2(idx);
ban[idx] = true;
i %= nPr(16 - j, d - 1 - j);
}
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cout << fixed << setprecision(20);
ll t;
cin >> t;
rep2(_, 0, t) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3632kb
input:
6 d 0 10 20 h 0 10 1f d 1 10 h 1 f d 1 1000000000 h 1 ffffffffffffffff
output:
10 f 9 e - -
result:
ok 6 lines
Test #2:
score: -100
Runtime Error
input:
50000 h 1 147a d 0 25 71 d 1 3587 d 0 26922 51887 d 1 711 d 0 3 5 h 0 7bf2defab442a0b1 f299a4cf1d4d9bed d 0 6961 91018 d 1 4 d 1 876 h 1 12cc5d3370f99120 d 1 161315 h 0 25f 6959 d 0 467 516 d 1 298 h 1 70260cdc2da73281 h 1 928e17d65d764ca2 h 1 c8ec8a7b67605e51 d 1 91697 d 0 4941925161850941148 89850...
output:
- 45 9072 3 983bbbac000 24561 3