QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#19152#2393. Alien IntegersQingyuAC ✓4ms3808kbC++201.8kb2022-01-28 11:51:342022-05-06 04:20:28

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-06 04:20:28]
  • 评测
  • 测评结果:AC
  • 用时:4ms
  • 内存:3808kb
  • [2022-01-28 11:51:34]
  • 提交

answer

#include <bits/stdc++.h>

int main() {
	long long n, _n;
	std::cin >> n;
	_n = n;
	int len = 0;
	std::vector<int> used_digits(10), digit;
	std::vector<int> available_digits;
	while (_n) {
		used_digits[_n % 10] = 1;
		digit.push_back(_n % 10);
		_n /= 10;
		++len;
	}
	std::reverse(digit.begin(), digit.end());
	for (int i = 0; i < 10; ++i)
		if (!used_digits[i])
			available_digits.push_back(i);
	if (available_digits.size() == 0) {
		puts("Impossible");
		return 0;
	}
	if (available_digits.size() == 1 && !used_digits[0]) {
		puts("0");
		return 0;
	}
	else {
		auto solve1 = [&]() {
			for (int i = 0; i < available_digits.size(); ++i) {
				if (available_digits[i] > digit[0]) {
					long long ret = available_digits[i];
					for (int j = 0; j + 1 < len; ++j) {
						ret = ret * 10 + available_digits[0];
					}
					return ret;
				}
			}
			long long ans = 0;
			for (int i = 0; i <= len; ++i) {
				if (i == 0 && available_digits[0] == 0) {
					ans = ans * 10 + available_digits[1];
				}
				else {
					ans = ans * 10 + available_digits[0];
				}
			}
			return ans;
		};
		auto solve2 = [&]() {
			for (int i = (int)(available_digits.size()) - 1; i >= 0; --i) {
				if (available_digits[i] < digit[0]) {
					long long ret = available_digits[i];
					for (int j = 0; j + 1 < len; ++j) {
						ret = ret * 10 + available_digits.back();
					}
					return ret;	
				}
			}
			long long ans = 0;
			for (int j = 0; j + 1 < len; ++j)
				ans = ans * 10 + available_digits.back();
			return ans;
		};
		long long x1 = solve1(), x2 = solve2();
		long long d1 = std::abs(n - x1), d2 = std::abs(n - x2);
		if (d1 < d2) printf("%lld\n", x1);
		else if (d2 < d1) printf("%lld\n", x2);
		else {
			printf("%lld %lld\n", x2, x1);
		}
	}
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3616kb

input:

1

output:

0 2

result:

ok single line: '0 2'

Test #2:

score: 0
Accepted
time: 3ms
memory: 3740kb

input:

394444

output:

288888 500000

result:

ok single line: '288888 500000'

Test #3:

score: 0
Accepted
time: 3ms
memory: 3672kb

input:

605555

output:

499999 711111

result:

ok single line: '499999 711111'

Test #4:

score: 0
Accepted
time: 3ms
memory: 3760kb

input:

944444

output:

888888 1000000

result:

ok single line: '888888 1000000'

Test #5:

score: 0
Accepted
time: 3ms
memory: 3672kb

input:

394444444444444

output:

288888888888888 500000000000000

result:

ok single line: '288888888888888 500000000000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3672kb

input:

605555555555555

output:

499999999999999 711111111111111

result:

ok single line: '499999999999999 711111111111111'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

944444444444444

output:

888888888888888 1000000000000000

result:

ok single line: '888888888888888 1000000000000000'

Test #8:

score: 0
Accepted
time: 3ms
memory: 3672kb

input:

1000000000000000

output:

999999999999999

result:

ok single line: '999999999999999'

Test #9:

score: 0
Accepted
time: 3ms
memory: 3696kb

input:

102030405060708

output:

99999999999999

result:

ok single line: '99999999999999'

Test #10:

score: 0
Accepted
time: 3ms
memory: 3668kb

input:

807060504030201

output:

999999999999999

result:

ok single line: '999999999999999'

Test #11:

score: 0
Accepted
time: 3ms
memory: 3760kb

input:

11111111111111

output:

9999999999999

result:

ok single line: '9999999999999'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

4

output:

3 5

result:

ok single line: '3 5'

Test #13:

score: 0
Accepted
time: 2ms
memory: 3720kb

input:

2222222222222

output:

1999999999999

result:

ok single line: '1999999999999'

Test #14:

score: 0
Accepted
time: 3ms
memory: 3548kb

input:

1999999999999

output:

2000000000000

result:

ok single line: '2000000000000'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

100000000000009

output:

88888888888888

result:

ok single line: '88888888888888'

Test #16:

score: 0
Accepted
time: 3ms
memory: 3612kb

input:

90000000000001

output:

88888888888888

result:

ok single line: '88888888888888'

Test #17:

score: 0
Accepted
time: 3ms
memory: 3644kb

input:

9876543210000

output:

Impossible

result:

ok single line: 'Impossible'

Test #18:

score: 0
Accepted
time: 1ms
memory: 3516kb

input:

112233440056789

output:

Impossible

result:

ok single line: 'Impossible'

Test #19:

score: 0
Accepted
time: 4ms
memory: 3472kb

input:

998877661123450

output:

Impossible

result:

ok single line: 'Impossible'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

912357890016129

output:

444444444444444

result:

ok single line: '444444444444444'

Test #21:

score: 0
Accepted
time: 3ms
memory: 3672kb

input:

189765003210110

output:

44444444444444

result:

ok single line: '44444444444444'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

778899023235656

output:

1111111111111111

result:

ok single line: '1111111111111111'

Test #23:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

5

output:

4 6

result:

ok single line: '4 6'

Test #24:

score: 0
Accepted
time: 3ms
memory: 3548kb

input:

333301467899999

output:

255555555555555

result:

ok single line: '255555555555555'

Test #25:

score: 0
Accepted
time: 1ms
memory: 3764kb

input:

433301467899999

output:

522222222222222

result:

ok single line: '522222222222222'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

274613689526294

output:

0

result:

ok single line: '0'

Test #27:

score: 0
Accepted
time: 3ms
memory: 3752kb

input:

340039250762387

output:

111111111111111

result:

ok single line: '111111111111111'

Test #28:

score: 0
Accepted
time: 3ms
memory: 3760kb

input:

136418797906598

output:

222222222222222

result:

ok single line: '222222222222222'

Test #29:

score: 0
Accepted
time: 2ms
memory: 3760kb

input:

161072428972852

output:

33333333333333

result:

ok single line: '33333333333333'

Test #30:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

589602035803718

output:

444444444444444

result:

ok single line: '444444444444444'

Test #31:

score: 0
Accepted
time: 2ms
memory: 3752kb

input:

146863487601092

output:

55555555555555

result:

ok single line: '55555555555555'

Test #32:

score: 0
Accepted
time: 3ms
memory: 3672kb

input:

350039125347282

output:

66666666666666

result:

ok single line: '66666666666666'

Test #33:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

652956153048838

output:

777777777777777

result:

ok single line: '777777777777777'

Test #34:

score: 0
Accepted
time: 3ms
memory: 3704kb

input:

9

output:

8 10

result:

ok single line: '8 10'

Test #35:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

421200497362543

output:

88888888888888

result:

ok single line: '88888888888888'

Test #36:

score: 0
Accepted
time: 3ms
memory: 3736kb

input:

867410302085138

output:

999999999999999

result:

ok single line: '999999999999999'

Test #37:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

223344556677889

output:

111111111111111

result:

ok single line: '111111111111111'

Test #38:

score: 0
Accepted
time: 3ms
memory: 3716kb

input:

110044556677889

output:

33333333333333

result:

ok single line: '33333333333333'

Test #39:

score: 0
Accepted
time: 3ms
memory: 3708kb

input:

110022336677889

output:

55555555555555

result:

ok single line: '55555555555555'

Test #40:

score: 0
Accepted
time: 2ms
memory: 3548kb

input:

110022334455889

output:

77777777777777

result:

ok single line: '77777777777777'

Test #41:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

110022334455667

output:

99999999999999

result:

ok single line: '99999999999999'

Test #42:

score: 0
Accepted
time: 3ms
memory: 3756kb

input:

442233116677889

output:

500000000000000

result:

ok single line: '500000000000000'

Test #43:

score: 0
Accepted
time: 3ms
memory: 3808kb

input:

220033445577889

output:

166666666666666

result:

ok single line: '166666666666666'

Test #44:

score: 0
Accepted
time: 2ms
memory: 3616kb

input:

330011445566889

output:

277777777777777

result:

ok single line: '277777777777777'

Test #45:

score: 0
Accepted
time: 3ms
memory: 3640kb

input:

10

output:

9

result:

ok single line: '9'

Test #46:

score: 0
Accepted
time: 3ms
memory: 3616kb

input:

770022445566119

output:

833333333333333

result:

ok single line: '833333333333333'

Test #47:

score: 0
Accepted
time: 3ms
memory: 3616kb

input:

550022331166778

output:

499999999999999

result:

ok single line: '499999999999999'

Test #48:

score: 0
Accepted
time: 1ms
memory: 3736kb

input:

94

output:

88 100

result:

ok single line: '88 100'

Test #49:

score: 0
Accepted
time: 3ms
memory: 3616kb

input:

394

output:

288 500

result:

ok single line: '288 500'

Test #50:

score: 0
Accepted
time: 1ms
memory: 3552kb

input:

944

output:

888 1000

result:

ok single line: '888 1000'

Test #51:

score: 0
Accepted
time: 3ms
memory: 3740kb

input:

999

output:

1000

result:

ok single line: '1000'

Test #52:

score: 0
Accepted
time: 3ms
memory: 3592kb

input:

123456789

output:

0

result:

ok single line: '0'