QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#914409 | #7912. Fixing Fractions | enze | AC ✓ | 427ms | 156888kb | C++20 | 3.1kb | 2025-02-25 12:54:15 | 2025-02-25 12:54:15 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
const ld pi = 3.14159265358979323846;
const int mod = (int)1e9 + 7;
const ll INF = 1e18;
template<typename T>
T chmax(T a, T b) {
return a > b ? a : b;
}
template<typename T>
T chmin(T a, T b) {
return a > b ? b : a;
}
const int N = (int)2e5 + 1, M = N * 2;
using i128 = __int128;
ostream &operator<<(std::ostream &os, i128 n) {
std::string s;
while (n) {
s += '0' + n % 10;
n /= 10;
}
std::reverse(s.begin(), s.end());
return os << s;
}
void solve(){
ll a, b, c, d;
cin >> a >> b >> c >> d;
ll gcd = __gcd(c, d);
c /= gcd;
d /= gcd;
map<i128, map<string, int>> mp1, mp2;
auto get = [&](ll a) -> pair<vector<ll>, vector<string>>{
vector<ll> A;
vector<string> T;
string s = to_string(a);
int n = s.size();
for(int i = 0; i < 1 << n; i++){
ll qwq = 0;
for(int j = 0; j < n; j++){
if(i >> j & 1){
qwq = qwq * 10 + (s[j] - '0');
}
}
if(qwq == 0){
continue;
}
A.pb(qwq);
string cur = to_string(qwq), miss = "";
int l = 0, r = 0;
for(; l < n && r < cur.size() && l < s.size(); ){
if(s[l] == cur[r]){
l++;
r++;
}
else{
miss += s[l];
l++;
}
}
for(int i = l; i < s.size(); i++){
miss += s[i];
}
sort(miss.begin(), miss.end());
T.pb(miss);
}
return {A, T};
};
auto p1 = get(a), p2 = get(b);
for(int i = 0; i < p1.first.size(); i++){
mp1[p1.first[i]][p1.second[i]] = 1;
}
for(int i = 0; i < p2.first.size(); i++){
mp2[p2.first[i]][p2.second[i]] = 1;
}
for(int i = 0; i < p1.first.size(); i++){
i128 p = p1.first[i];
if(p * d % c == 0){
p = p * d / c;
i128 q = p;
if(mp2[q][p1.second[i]]){
cout << "possible" << endl;
cout << p1.first[i] << " " << q << endl;
return;
}
}
}
for(int i = 0; i < p2.first.size(); i++){
i128 p = p2.first[i];
if(p * c % d == 0){
p = p * c / d;
i128 q = p;
if(mp1[q][p2.second[i]]){
cout << "possible" << endl;
cout << p2.first[i] << " " << q << endl;
return;
}
}
}
cout << "impossible" << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
// cin >> t;
while(t--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3712kb
input:
163 326 1 2
output:
possible 1 2
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
871 1261 13 39
output:
possible 87 261
result:
ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
123 267 12339 23679
output:
impossible
result:
ok
Test #4:
score: 0
Accepted
time: 427ms
memory: 156888kb
input:
123451234512345123 123451234512345124 121212121212121212 121212121212121212
output:
impossible
result:
ok
Test #5:
score: 0
Accepted
time: 196ms
memory: 66320kb
input:
164611082380207350 481860429901255935 113810935861979620 336362576676703390
output:
possible 164610823730 486499125935
result:
ok
Test #6:
score: 0
Accepted
time: 134ms
memory: 46756kb
input:
339214413235389043 38435363395032414 876803448566180874 154200710389942324
output:
possible 321459 56534
result:
ok
Test #7:
score: 0
Accepted
time: 86ms
memory: 40016kb
input:
899999999999999998 999999999999999998 999999999999999999 999999999999999999
output:
impossible
result:
ok
Test #8:
score: 0
Accepted
time: 77ms
memory: 40048kb
input:
999999999999999999 999999999999999998 999999999999999997 999999999999999996
output:
impossible
result:
ok
Test #9:
score: 0
Accepted
time: 76ms
memory: 40228kb
input:
999999999999999998 999999999999999999 999999999999999996 999999999999999997
output:
impossible
result:
ok
Test #10:
score: 0
Accepted
time: 78ms
memory: 39940kb
input:
699999999999999979 699999999999999972 9999999999999997 9999999999999996
output:
possible 69999999999999979 69999999999999972
result:
ok
Test #11:
score: 0
Accepted
time: 76ms
memory: 40224kb
input:
699999999999999972 699999999999999979 9999999999999996 9999999999999997
output:
possible 69999999999999972 69999999999999979
result:
ok
Test #12:
score: 0
Accepted
time: 76ms
memory: 40192kb
input:
569999999999999979 569999999999999972 9999999999999997 9999999999999996
output:
possible 69999999999999979 69999999999999972
result:
ok
Test #13:
score: 0
Accepted
time: 79ms
memory: 39996kb
input:
569999999999999972 569999999999999979 9999999999999996 9999999999999997
output:
possible 69999999999999972 69999999999999979
result:
ok
Test #14:
score: 0
Accepted
time: 242ms
memory: 86224kb
input:
615463967153146625 625329650586180138 8792342387592375 8904235798025734
output:
possible 61546396713146625 62329650586180138
result:
ok
Test #15:
score: 0
Accepted
time: 231ms
memory: 86364kb
input:
625329650586180138 615463967153146625 8904235798025734 8792342387592375
output:
possible 62329650586180138 61546396713146625
result:
ok
Test #16:
score: 0
Accepted
time: 72ms
memory: 40164kb
input:
999999999999999999 999999999999999998 9 8
output:
possible 9 8
result:
ok
Test #17:
score: 0
Accepted
time: 72ms
memory: 40272kb
input:
999999999999999998 999999999999999999 8 9
output:
possible 8 9
result:
ok
Test #18:
score: 0
Accepted
time: 83ms
memory: 40040kb
input:
999999999999999999 999999999999999998 9 9
output:
impossible
result:
ok
Test #19:
score: 0
Accepted
time: 81ms
memory: 40088kb
input:
999999999999999998 999999999999999999 9 9
output:
impossible
result:
ok
Test #20:
score: 0
Accepted
time: 145ms
memory: 44748kb
input:
999999999999999999 590897978349414785 1 9999999
output:
impossible
result:
ok
Test #21:
score: 0
Accepted
time: 147ms
memory: 44804kb
input:
590897978349414785 999999999999999999 9999999 1
output:
impossible
result:
ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
103 301 1 1010
output:
impossible
result:
ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
301 103 1010 1
output:
impossible
result:
ok
Test #24:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
10 10 1 1010
output:
impossible
result:
ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
10 10 1010 1
output:
impossible
result:
ok
Test #26:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
10 100 1 1010
output:
impossible
result:
ok
Test #27:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
100 10 1010 1
output:
impossible
result:
ok
Test #28:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
101 101 1 10
output:
impossible
result:
ok
Test #29:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
101 101 10 1
output:
impossible
result:
ok
Test #30:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
101 103 271 383
output:
impossible
result:
ok
Test #31:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
103 101 383 271
output:
impossible
result:
ok
Test #32:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
101 103 2 2
output:
impossible
result:
ok
Test #33:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
103 101 2 2
output:
impossible
result:
ok
Test #34:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
1 2 3 4
output:
impossible
result:
ok
Test #35:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
2 1 4 3
output:
impossible
result:
ok
Test #36:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
1 2 2 4
output:
possible 1 2
result:
ok
Test #37:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
2 1 4 2
output:
possible 2 1
result:
ok
Test #38:
score: 0
Accepted
time: 166ms
memory: 51264kb
input:
871736332925593729 543733447277867389 610234330479156103 380613413094507523
output:
possible 87176332925593729 54373344727786789
result:
ok
Test #39:
score: 0
Accepted
time: 126ms
memory: 41656kb
input:
240074419443591671 13191802693005035 720223258330775013 39575408079015105
output:
possible 240074419443591671 13191802693005035
result:
ok
Test #40:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
87285 67528 350301584700586616 262726188525439962
output:
possible 8 6
result:
ok
Test #41:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
25167 57632 70990028241498705 212970084724496115
output:
possible 1 3
result:
ok
Test #42:
score: 0
Accepted
time: 178ms
memory: 55580kb
input:
255378660878394793 633036524778728433 281356712406942263 184068083292890503
output:
possible 57889793 37872433
result:
ok
Test #43:
score: 0
Accepted
time: 179ms
memory: 55172kb
input:
178249554695517007 775571947654578727 185397750440420700 739143080814301059
output:
possible 189555100 755717587
result:
ok
Test #44:
score: 0
Accepted
time: 183ms
memory: 70208kb
input:
213528472930234749 85492482554697201 220147855594695219 88588495138927101
output:
possible 213528472933749 85924825546971
result:
ok
Test #45:
score: 0
Accepted
time: 174ms
memory: 58312kb
input:
229667837504492150 423823230390052593 139171825675675650 111797337607063763
output:
possible 29667837492150 23832303902593
result:
ok
Test #46:
score: 0
Accepted
time: 202ms
memory: 66240kb
input:
959724992407703072 279935791504023095 21196383527844000 23000777243214600
output:
possible 729407700 791500305
result:
ok
Test #47:
score: 0
Accepted
time: 188ms
memory: 57716kb
input:
737230031890668611 477527391841134652 487876079695929176 316638986126201872
output:
possible 73230080666 47527434652
result:
ok
Test #48:
score: 0
Accepted
time: 211ms
memory: 73016kb
input:
821918197233093547 482769317307268088 735625367131973206 437264673126743024
output:
possible 819181923309547 486931707268088
result:
ok
Test #49:
score: 0
Accepted
time: 209ms
memory: 72408kb
input:
986575520654615089 832454676640259790 337509828395294952 166649313778905858
output:
possible 6575525108 3246740257
result:
ok
Test #50:
score: 0
Accepted
time: 156ms
memory: 47292kb
input:
307743411018585120 777648960327944337 92230233055755360 232946880983833011
output:
possible 30743411018585120 77648960327944337
result:
ok
Test #51:
score: 0
Accepted
time: 181ms
memory: 56624kb
input:
332608543750002007 276331967922786123 997825631250006021 828995903768358369
output:
possible 332608543750002007 276331967922786123
result:
ok
Test #52:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
42961 12691 140676414960799412 35169103740199853
output:
possible 4 1
result:
ok
Test #53:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
60319 3698 21569487492882474 172555899943059792
output:
impossible
result:
ok
Test #54:
score: 0
Accepted
time: 171ms
memory: 48240kb
input:
919522355898441116 925429118112538684 878863045408683820 259033318646769968
output:
possible 95 28
result:
ok
Test #55:
score: 0
Accepted
time: 175ms
memory: 55388kb
input:
101968312761156453 354766411968506111 521968566838241168 347582185051245616
output:
possible 821153 546811
result:
ok
Test #56:
score: 0
Accepted
time: 182ms
memory: 57848kb
input:
528417717535325516 561236080990898053 417450042529068764 492650398280946187
output:
possible 5284177753532516 6236080990898053
result:
ok
Test #57:
score: 0
Accepted
time: 172ms
memory: 60116kb
input:
574673779185490734 711411136579217223 969474686859223048 192506366913103201
output:
possible 574673791854904 114111657921223
result:
ok
Test #58:
score: 0
Accepted
time: 186ms
memory: 58364kb
input:
182845432626604133 199481192014186083 645684048212754369 155713417458044819
output:
possible 82854362660433 19981190486083
result:
ok
Test #59:
score: 0
Accepted
time: 214ms
memory: 73496kb
input:
162889468229577653 514956283267729831 544191139194939684 230473644567719889
output:
possible 876 371
result:
ok
Test #60:
score: 0
Accepted
time: 233ms
memory: 82572kb
input:
240381750760576242 547914590638611901 218942727272915976 538700892374194308
output:
possible 24038507605722 59145903861901
result:
ok
Test #61:
score: 0
Accepted
time: 98ms
memory: 32484kb
input:
494477002138544562 5339543420789844 943444195109271036 7068065112669744
output:
possible 447021846 3348984
result:
ok
Test #62:
score: 0
Accepted
time: 157ms
memory: 42848kb
input:
123212321232123212 123212321232123212 123212321232123212 123212321232123213
output:
impossible
result:
ok
Test #63:
score: 0
Accepted
time: 174ms
memory: 53380kb
input:
123123123123123123 123123123123123123 123123123123123123 123123123123123121
output:
impossible
result:
ok
Test #64:
score: 0
Accepted
time: 226ms
memory: 60868kb
input:
123212321232123213 123212321232123214 121212121212121212 121212121212121212
output:
impossible
result:
ok
Test #65:
score: 0
Accepted
time: 225ms
memory: 57120kb
input:
123212321232123212 123212321232123213 121212121212121212 121212121212121212
output:
impossible
result:
ok
Test #66:
score: 0
Accepted
time: 356ms
memory: 127232kb
input:
123412341234123412 123412341234123415 121212121212121212 121212121212121212
output:
impossible
result:
ok
Test #67:
score: 0
Accepted
time: 266ms
memory: 113060kb
input:
123456123456123456 654321654321654321 121212121212121212 121212121212121213
output:
impossible
result:
ok
Test #68:
score: 0
Accepted
time: 269ms
memory: 121264kb
input:
123456789123456789 987654321987654321 121212121212121212 121212121212121213
output:
impossible
result:
ok
Test #69:
score: 0
Accepted
time: 109ms
memory: 40188kb
input:
121212121212121212 121212121212121212 121212121212121212 121212121212121213
output:
impossible
result:
ok
Test #70:
score: 0
Accepted
time: 239ms
memory: 74412kb
input:
121314151617181912 213141516171819121 2 1
output:
impossible
result:
ok
Test #71:
score: 0
Accepted
time: 109ms
memory: 40036kb
input:
112112112112112112 211211211211211211 1 2
output:
impossible
result:
ok
Test #72:
score: 0
Accepted
time: 109ms
memory: 40188kb
input:
121212121212121212 212121212121212121 121212121212121212 121212121212121213
output:
impossible
result:
ok
Test #73:
score: 0
Accepted
time: 98ms
memory: 40240kb
input:
121212111212121121 111212121112121212 121212121212121212 121212121212121213
output:
impossible
result:
ok
Test #74:
score: 0
Accepted
time: 104ms
memory: 39948kb
input:
112212112212121122 212112212211221121 121212121212121212 121212121212121213
output:
impossible
result:
ok