QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#19152 | #2393. Alien Integers | Qingyu | AC ✓ | 4ms | 3808kb | C++20 | 1.8kb | 2022-01-28 11:51:34 | 2022-05-06 04:20:28 |
Judging History
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'