QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#719179#2519. Number with Bachelorsyuto1115#WA 21ms4024kbC++202.6kb2024-11-06 23:07:072024-11-06 23:07:08

Judging History

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

  • [2024-11-06 23:07:08]
  • 评测
  • 测评结果:WA
  • 用时:21ms
  • 内存:4024kb
  • [2024-11-06 23:07:07]
  • 提交

answer

#include <cstdio>
#include <cstring>
#include <vector>

const int N = 25;
int n, base[2] = {10, 16};
unsigned long long dp[N][N], leqlen[N][N];

int fromchar(char c) {
	if (c <= '9' && c >= '0') return c - '0';
	else return c - 'a' + 10;
}

char tochar(int c) {
	if (c >= 10) return 'a' + c - 10;
	return '0' + c;
}

void outhex(unsigned long long x) {
	if (!x) {
		printf("0");
		return;
	}
	std::vector<int> repr;
	while (x) {
		repr.push_back(x % 16);
		x /= 16;
	}
	for (int i = (int)repr.size() - 1; i >= 0; --i) {
		int c = repr[i];
		if (c < 10) printf("%d", c);
		else printf("%c", 'a' + c - 10);
	}
	printf("\n");
}

unsigned long long readhex() {
	char s[N];
	scanf("%s", s);
	unsigned long long r = 0;
	for (int i = 0; s[i]; ++i) {
		r *= 16;
		r += fromchar(s[i]);
	}
	return r;
}

unsigned long long f(const char *s, int b, bool last) {
	if (s[0] == '0') return last;
	int len = strlen(s), avail = base[b];
	bool u[N] = {0};
	unsigned long long ans = leqlen[len - 1][avail];
	for (int i = 0; s[i]; ++i) {
		int c = fromchar(s[i]);
		if (avail - i - 1 < 0) return ans;
		for (int j = 0 + (!i); j < c; ++j) if (!u[j]) ans += dp[len - i - 1][avail - i - 1];
		if (u[c]) return ans;
		u[c] = true;
	}
	return ans + (unsigned long long)last;
}

void solve(unsigned long long ind, bool b) {
	if (ind == 1) {
		printf("0\n");
		return;
	}
	int len, avail = base[b];
	--ind;
	for (len = 0; len < N && leqlen[len][avail] <= ind; ++len);
	if (len == N) printf("-\n");
	else {
		ind -= leqlen[len - 1][avail];
		bool u[N] = {0};
		for (int i = 0; i < len; ++i) {
			int j = 0;
			if (!i) ++j;
			--avail;
			for (; dp[len - i - 1][avail] <= ind; ++j) {
				if (!u[j]) ind -= dp[len - i - 1][avail];
			}
			while (u[j]) ++j;
			printf("%c", tochar(j));
			u[j] = 1;
		}
		printf("\n");
	}
}
#include <random>

int main() {
	for (int i = 0; i < N; ++i) {
		for (int j = i; j < N; ++j) {
			if (!i) dp[i][j] = leqlen[i][j] = 1;
			else {
				dp[i][j] = j * dp[i - 1][j - 1];
				leqlen[i][j] = leqlen[i - 1][j] + dp[i - 1][j - 1] * (j - 1);
			}
		}
	}
	scanf("%d", &n);
	/*
	std::mt19937 rng(228);
	while (n--) {
		int x = rng() % 100;
		printf("%d: f %llu ", x, f(std::to_string(x).c_str(), 0, 1));
		solve(x, 0);
	}
	return 0;
	*/
	while (n--) {
		int type;
		char b;
		scanf(" %c%d", &b, &type);
		b = b == 'd' ? 0 : 1;
		if (type == 0) {
			char l[N], r[N];
			scanf("%s%s", l, r);
			unsigned long long ans = f(r, b, 1) - f(l, b, 0);
			if (b == 1) outhex(ans);
			else printf("%llu\n", ans);
		} else {
			unsigned long long ind;
			if (b == 1) ind = readhex();
			else scanf("%llu", &ind);
			solve(ind, b);
		}
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3776kb

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
Wrong Answer
time: 21ms
memory: 4024kb

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:

1b36
43
6587
7710
953
3
8daab378500
26054
3
1356
-
946307
4681
40
387
-
-
-
491850
0
1
29
-
4605298
1
1
-
15b4
175f
9b944134000
124b7
6279
9
6257
-
39be22a900
5c636b59300
146ce
2a55
-
0
-
7
d
6
2041
-
1c94afe7300
0
5
9149
16540973
1389
125
0
-
3bc31189480
424
66800
7
-
-
1e6
0
0
48b6
9
-
2b0
5019
14...

result:

wrong answer 7758th lines differ - expected: '0', found: '020459'