QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#86644#1875. Neinle0nWA 35ms2952kbC++141.7kb2023-03-10 14:37:472023-03-10 14:37:49

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-10 14:37:49]
  • 评测
  • 测评结果:WA
  • 用时:35ms
  • 内存:2952kb
  • [2023-03-10 14:37:47]
  • 提交

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'