QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#86644 | #1875. Nein | le0n | WA | 35ms | 2952kb | C++14 | 1.7kb | 2023-03-10 14:37:47 | 2023-03-10 14:37:49 |
Judging History
answer
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
struct i250
{
__int128 x, y;
i250(__int128 x0 = 0)
{
x = x0;
y = 0;
}
i250(__int128 x0, __int128 y0)
{
x = x0;
y = y0;
}
i250 operator + (i250 in)
{
if(x + in.x >= ((__int128)(1) << ((__int128)126)))
return i250(x + in.x - ((__int128)(1) << ((__int128)126)), y + in.y + 1);
return i250(x + in.x, y + in.y);
}
};
i250 DP[65][652];
__int128 p10[42];
int F[251];
int wow[65];
int main()
{
ll x;
int k, i, j, a, b, c, d, e, f, B;
__int128 n;
__int128 ans = 0, p = 1, T;
scanf("%d%lld", &k, &x);
n = x;
for(i = 1; i <= k; i++)
p *= 10;
p10[0] = 1;
for(i = 1; i <= 36; i++)
p10[i] = p10[i - 1] * 10;
p--;
B = 40 / k + 1;
for(i = 0; i < (ll)k * B; i++)
for(j = 0; j < 9; j++)
{
wow[i] = j;
f = 0;
for(a = 1; a < B; a++)
{
T = p * a;
memset(DP, 0, sizeof(DP));
for(b = 0; b < k; b++)
{
if(b)
for(c = 0; c <= B; c++)
DP[b][c * 10 + (T / p10[k - b - 1]) % 10] = DP[b - 1][c];
else
DP[0][T / p10[k - 1]] = i250(1);
for(c = 0; c < B; c++)
for(d = 0; d <= 10 * B; d++)
if(c * k + b <= i)
DP[b][d] = DP[b][d + wow[c * k + b]];
else
for(e = 1; e < 9; e++)
DP[b][d] = DP[b][d] + DP[b][d + e];
}
if(DP[k - 1][0].x >= n || DP[k - 1][0].y)
{
f = 1;
break;
}
n -= DP[k - 1][0].x;
}
if(f)
break;
}
for(i = 0; i < (ll)k * B; i++)
ans = 10 * ans + wow[i];
ans /= p;
c = 0;
while(ans)
{
F[++c] = ans % 10;
ans /= 10;
}
for(i = c; i >= 1; i--)
printf("%d", F[i]);
printf("\n");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 33ms
memory: 2952kb
input:
1 1
output:
2
result:
ok answer is '2'
Test #2:
score: 0
Accepted
time: 35ms
memory: 2864kb
input:
1 8
output:
9
result:
ok answer is '9'
Test #3:
score: 0
Accepted
time: 33ms
memory: 2880kb
input:
1 9
output:
12
result:
ok answer is '12'
Test #4:
score: 0
Accepted
time: 34ms
memory: 2948kb
input:
1 10
output:
13
result:
ok answer is '13'
Test #5:
score: 0
Accepted
time: 26ms
memory: 2920kb
input:
5 1
output:
11112
result:
ok answer is '11112'
Test #6:
score: 0
Accepted
time: 25ms
memory: 2948kb
input:
5 84
output:
11235
result:
ok answer is '11235'
Test #7:
score: 0
Accepted
time: 22ms
memory: 2944kb
input:
5 668
output:
12345
result:
ok answer is '12345'
Test #8:
score: 0
Accepted
time: 22ms
memory: 2876kb
input:
5 733942
output:
2281488
result:
ok answer is '2281488'
Test #9:
score: 0
Accepted
time: 19ms
memory: 2880kb
input:
18 528599760553218747
output:
30725517742188427234
result:
ok answer is '30725517742188427234'
Test #10:
score: 0
Accepted
time: 21ms
memory: 2864kb
input:
18 964828716126767591
output:
55758681752658348563
result:
ok answer is '55758681752658348563'
Test #11:
score: 0
Accepted
time: 20ms
memory: 2940kb
input:
18 401057671700316435
output:
22687686284122211545
result:
ok answer is '22687686284122211545'
Test #12:
score: 0
Accepted
time: 25ms
memory: 2864kb
input:
18 837286627273865280
output:
48255733668453323265
result:
ok answer is '48255733668453323265'
Test #13:
score: 0
Accepted
time: 20ms
memory: 2856kb
input:
18 273515582847414124
output:
15116382182883344554
result:
ok answer is '15116382182883344554'
Test #14:
score: 0
Accepted
time: 23ms
memory: 2872kb
input:
18 55923968082999579
output:
2876461768512185545
result:
ok answer is '2876461768512185545'
Test #15:
score: -100
Wrong Answer
time: 31ms
memory: 2936kb
input:
8 715524960511324231
output:
12022650240444127856
result:
wrong answer expected '12022650248772112989', found '12022650240444127856'