QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#914409#7912. Fixing FractionsenzeAC ✓427ms156888kbC++203.1kb2025-02-25 12:54:152025-02-25 12:54:15

Judging History

This is the latest submission verdict.

  • [2025-02-25 12:54:15]
  • Judged
  • Verdict: AC
  • Time: 427ms
  • Memory: 156888kb
  • [2025-02-25 12:54:15]
  • Submitted

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