QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #686360 | #1875. Nein | user10086 | Compile Error | / | / | C++23 | 1.7kb | 2024-10-29 11:42:43 | 2024-10-29 11:42:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 38;
#define int __uint128
int f[N][N * 10];
void pre()
{
f[0][0] = 1;
for (int i = 0; i + 1 < N; i++)
for (int j = 0; j < N * 8; j++)
if (f[i][j]) for (int k = 0; k <= 8; k++)
assert(j + k < N * 8), f[i + 1][j + k] += f[i][j];
}
long long k, sz[N];
int pw[N];
long long x;
bool vis[N][N * 10];
int dp[N][N * 10];
int dfs(int tar, int cur, int c)
{
// printf("dfs(%lld, %lld, %lld)\n", tar, cur, c);
if (cur >= k) return c == tar;
if (vis[cur][c]) return dp[cur][c];
vis[cur][c] = true, dp[cur][c] = 0;
for (int j = 0; j < N * 8; j++)
{
if (!f[sz[cur]][j] || (c + j) % 10 != tar % 10) continue;
// printf("put %lld:\n", j);
dp[cur][c] += f[sz[cur]][j] * dfs(tar / 10, cur + 1, (c + j) / 10);
}
// printf("dfs(%lld, %lld, %lld) = %lld\n", tar, cur, c, dp[cur][c]);
return dp[cur][c];
}
signed main()
{
cin >> k >> x; x++;
pre();
for (int i = 0; i <= N - 1; i++) sz[i % k]++;
pw[0] = 1; for (int i = 1; i < N; i++) pw[i] = pw[i - 1] * 10;
vector<int> sol;
int cur = 0;
for (int i = N - 1; i >= 0; i--)
{
for (int j = 0; ; j++)
{
assert(j <= 8);
cur += j * pw[i % k], sz[i % k]--;
// printf("i = %lld, j = %lld\n", i, j);
int c = 0;
for (int p = 0; p < N; p++)
{
int tar = p * (pw[k] - 1) - cur;
if (tar < 0) continue;
memset(vis, 0, sizeof vis);
c += dfs(tar, 0, 0);
}
// printf("c = %lld\n", c);
if (x <= c)
{
sol.push_back(j);
break;
}
else x -= c, sz[i % k]++, cur -= j * pw[i % k];
}
}
int tmp = 0; for (int x : sol) tmp = tmp * 10 + x;
// cout << tmp << ' ' << (pw[k] - 1) << endl;
cout << (long long)(tmp / (pw[k] - 1));
}
Details
answer.code:7:13: error: ‘__uint128’ does not name a type; did you mean ‘__int128’?
7 | #define int __uint128
| ^~~~~~~~~
answer.code:9:1: note: in expansion of macro ‘int’
9 | int f[N][N * 10];
| ^~~
answer.code: In function ‘void pre()’:
answer.code:13:9: error: ‘f’ was not declared in this scope
13 | f[0][0] = 1;
| ^
answer.code:7:13: error: ‘__uint128’ was not declared in this scope; did you mean ‘__int128’?
7 | #define int __uint128
| ^~~~~~~~~
answer.code:14:14: note: in expansion of macro ‘int’
14 | for (int i = 0; i + 1 < N; i++)
| ^~~
answer.code:14:25: error: ‘i’ was not declared in this scope
14 | for (int i = 0; i + 1 < N; i++)
| ^
answer.code:15:26: error: expected ‘;’ before ‘j’
15 | for (int j = 0; j < N * 8; j++)
| ^
answer.code:15:33: error: ‘j’ was not declared in this scope; did you mean ‘jn’?
15 | for (int j = 0; j < N * 8; j++)
| ^
| jn
answer.code:16:47: error: expected ‘;’ before ‘k’
16 | if (f[i][j]) for (int k = 0; k <= 8; k++)
| ^
answer.code:16:54: error: ‘k’ was not declared in this scope
16 | if (f[i][j]) for (int k = 0; k <= 8; k++)
| ^
answer.code: At global scope:
answer.code:7:13: error: ‘__uint128’ does not name a type; did you mean ‘__int128’?
7 | #define int __uint128
| ^~~~~~~~~
answer.code:21:1: note: in expansion of macro ‘int’
21 | int pw[N];
| ^~~
answer.code:7:13: error: ‘__uint128’ does not name a type; did you mean ‘__int128’?
7 | #define int __uint128
| ^~~~~~~~~
answer.code:25:1: note: in expansion of macro ‘int’
25 | int dp[N][N * 10];
| ^~~
answer.code:7:13: error: ‘__uint128’ does not name a type; did you mean ‘__int128’?
7 | #define int __uint128
| ^~~~~~~~~
answer.code:27:1: note: in expansion of macro ‘int’
27 | int dfs(int tar, int cur, int c)
| ^~~
answer.code: In function ‘int main()’:
answer.code:7:13: error: ‘__uint128’ was not declared in this scope; did you mean ‘__int128’?
7 | #define int __uint128
| ^~~~~~~~~
answer.code:47:14: note: in expansion of macro ‘int’
47 | for (int i = 0; i <= N - 1; i++) sz[i % k]++;
| ^~~
answer.code:47:25: error: ‘i’ was not declared in this scope
47 | for (int i = 0; i <= N - 1; i++) sz[i % k]++;
| ^
answer.code:48:9: error: ‘pw’ was not declared in this scope; did you mean ‘pow’?
48 | pw[0] = 1; for (int i = 1; i < N; i++) pw[i] = pw[i - 1] * 10;
| ^~
| pow
answer.code:7:13: error: ‘__uint128’ was not declared in this scope; did you mean ‘__int128’?
7 | #define int __uint128
| ^~~~~~~~~
answer.code:48:25: note: in expansion of macro ‘int’
48 | pw[0] = 1; for (int i = 1; i < N; i++) pw[i] = pw[i - 1] * 10;
| ^~~
answer.code:48:36: error: ‘i’ was not declared in this scope
48 | pw[0] = 1; for (int i = 1; i < N; i++) pw[i] = pw[i - 1] * 10;
| ^
answer.code:7:13: error: ‘__uint128’ was not declared in this scope; did you mean ‘__int128’?
7 | #define int __uint128
| ^~~~~~~~~
answer.code:49:16: note: in expansion of macro ‘int’
49 | vector<int> sol;
| ^~~
answer.code:49:19: error: template argument 1 is invalid
49 | vector<int> sol;
| ^
answer.code:49:19: error: template argument 2 is invalid
answer.code:50:13: error: expected ‘;’ before ‘cur’
50 | int cur = 0;
| ^~~
answer.code:51:18: error: expected ‘;’ before ‘i’
51 | for (int i = N - 1; i >= 0; i--)
| ^
answer.code:51:29: error: ‘i’ was not declared in this scope
51 | for (int i = N - 1; i >= 0; i--)
| ^
answer.code:53:26: error: expected ‘;’ before ‘j’
53 | for (int j = 0; ; j++)
| ^
answer.code:53:35: error: ‘j’ was not declared in this scope
53 | for (int j = 0; ; j++)
| ^
answer.code:56:25: error: ‘cur’ was not declared in this scope
56 | cur += j * pw[i % k], sz[i % k]--;
| ^~~
answer.code:58:29: error: expected ‘;’ before ‘c’
58 | int c = 0;
| ^
answer.code:59:34: error: expected ‘;’ before ‘p’
59 | for (int p = 0; p < N; p++)
|...