QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#429133#6519. X Equals Ydnialh#WA 295ms3748kbC++206.3kb2024-06-02 01:18:452024-06-02 01:18:45

Judging History

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

  • [2024-06-02 01:18:45]
  • 评测
  • 测评结果:WA
  • 用时:295ms
  • 内存:3748kb
  • [2024-06-02 01:18:45]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define F0R(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i <= b; i++)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define FORd(i,a,b) for (int i = (b); i >= (a); i--)
#define trav(a, x) for (auto& a : x)
#define rep(i, a, b) for(int i = a; i < (b); ++i)

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

const char nl = '\n';
const int MAX_N = 100011;
const ll INF = (1<<29) + 123;
const ll MOD = 1000000007; // 998244353
const ld PI = 4*atan((ld)1);

template <typename T> bool ckmin(T& a, const T& b) { return a > b ? a=b, 1 : 0; }
template <typename T> bool ckmax(T& a, const T& b) { return b > a ? a=b, 1 : 0; }

/**** Credit to chatgpt 4.0 ****/

// Stream operator for std::pair
template<typename T1, typename T2>
ostream& operator<<(ostream &out, const pair<T1, T2> &v) {
    out << "(" << v.first << ", " << v.second << ")"; 
    return out;
}

// Trait to check if a type is iterable
template<typename T, typename = void>
struct is_iterable : false_type {};

template<typename T>
struct is_iterable<T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>> : true_type {};

// Stream operator for iterable types excluding std::string
template<typename TT>
typename enable_if<is_iterable<TT>::value && !is_same<TT, string>::value, ostream&>::type
operator<<(ostream& out, const TT& c) {
    out << "{ ";
    for (const auto& x : c) out << x << " ";
    out << "}"; 
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, std::stack<T> container) {
    std::vector<T> elements;
    while (!container.empty()) {
        elements.push_back(container.top());
        container.pop();
    }
    std::reverse(elements.begin(), elements.end()); // Reverse to maintain order
    return out << elements;
}

template<typename T>
ostream& operator<<(ostream& out, std::queue<T> container) {
    std::vector<T> elements;
    while (!container.empty()) {
        elements.push_back(container.front());
        container.pop();
    }
    return out << elements;
}

// Helper function to print std::priority_queue
template<typename T, typename Container, typename Compare>
ostream& operator<<(ostream& out, std::priority_queue<T, Container, Compare> pq) {
    out << "{";
    while (!pq.empty()) {
        out << " " << pq.top();
        pq.pop();
    }
    out << " }";
    return out;
}

#ifdef DBG
void dbg_out() { cerr << endl; }

template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
    cerr << ' ' << H;
    dbg_out(T...);
}

#define dbg(...) cerr << #__VA_ARGS__ << ":", dbg_out(__VA_ARGS__);
#define dbg_array(a, n) cerr << #a << ": { "; for(int i = 0; i < n; i++) cerr << a[i] << " "; cerr << "}\n";
#else
#define dbg(...)
#define dbg_array(a, n)
#endif

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MX = 3e5+5;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--) {
        int x, y, A, B; cin >> x >> y >> A >> B;
        bool swapped = 0;
        if (x > y) {
            swap(x, y);
            swap(A, B);
            swapped = 1;
        }
        // brute force over all sqrt(x) and sqrt(y) possible bases
        map<vi, int> v_x, v_y;
        int i = 2;
        for (; i*i <= x; i++) {
            // convert x to base i
            vi cur;
            int X = x;
            while (X) {
                cur.pb(X%i);
                X /= i;
            }
            v_x[cur] = i;
        }
        int j = 2;
        for (; j*j <= y; j++) {
            // convert y to base j
            vi cur;
            int Y = y;
            while (Y) {
                cur.pb(Y%j);
                Y /= j;
            }
            v_y[cur] = j;
        }
        // check if there's a match between these two
        pi ans = {-1, -1};
        trav(v, v_x) {
            if (v_y.count(v.f)) {
                if (v.s <= A && v_y[v.f] <= B) {
                    ans = {v.s, v_y[v.f]};
                    break;
                }
            }
        }
        // now do the case where we have 1 digit between the two
        if (x == y) {
            int b = y+1;
            assert(b >= 2);
            if (b <= A && b <= B) {
                ans = {b, b};
            }
        }
        // now do the case of 2 digits
        // base for x has to be in [i, A]
        // base for y has to be in [j, B]
        int diff = y-x;
        if (diff == 0) {
            ans.f = ans.s = 2;
        } else {
            // try all divisors
            for (int k = 1; k*k <= diff; k++) {
                if (diff % k) continue;
                // divisors are k and diff/k
                // 2nd digit is k
                // a > k
                // 0 < x - k*a < a
                // (k+1)*a > x
                // a > x/(k+1)
                dbg(diff, k);
                int dig = k; // dig is the "tens" digit
                int a = max(x/(dig+1), dig)+1;
                int b = a+diff/dig;
                if (x-dig*a >= 0 && a >= i && a <= A && b >= j && b <= B) {
                    ans = {a, b};
                    break;
                }
                // now try it with 2nd digit being diff/k
                dig = diff/k;
                a = max(x/(dig+1), dig)+1;
                b = a+diff/dig;
                if (x- dig*a >= 0 && a >= i && a <= A && b >= j && b <= B) {
                    ans = {a, b};
                    break;
                }
            }
        }

        // the bases are between 
        if (ans.f == -1) cout << "NO" << nl;
        else {
            cout << "YES" << nl;
            assert(min(ans.f, ans.s) >= 2);
            assert(ans.f <= A && ans.s <= B);
            if (swapped) swap(ans.f, ans.s);
            cout << ans.f << " " << ans.s << nl;
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3532kb

input:

6
1 1 1000 1000
1 2 1000 1000
3 11 1000 1000
157 291 5 6
157 291 3 6
10126 114514 789 12345

output:

YES
2 2
NO
YES
2 10
YES
4 5
NO
YES
779 9478

result:

ok correct (6 test cases)

Test #2:

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

input:

1000
920 661 756 534
52 454 31 218
980 77 812 6
729 733 289 660
161 643 21 475
602 525 329 274
782 167 279 113
875 100 388 16
426 498 341 417
433 751 312 39
91 50 47 39
941 388 247 46
725 808 148 486
945 405 700 145
647 509 152 445
45 564 16 468
843 40 530 3
722 36 323 22
568 472 443 41
38 749 25 42...

output:

YES
590 331
YES
14 148
NO
YES
146 147
NO
YES
77 66
YES
247 42
NO
YES
214 286
NO
NO
NO
NO
YES
406 136
YES
96 73
YES
12 185
NO
NO
YES
34 28
YES
10 247
NO
NO
YES
193 17
YES
132 101
NO
YES
701 297
NO
YES
45 174
NO
YES
65 28
NO
NO
YES
89 49
YES
6 5
NO
NO
NO
NO
NO
YES
282 87
NO
YES
170 157
YES
146 346
YES...

result:

ok correct (1000 test cases)

Test #3:

score: -100
Wrong Answer
time: 295ms
memory: 3748kb

input:

1000
312788 308299 292039 230765
263760 329714 198045 86472
945524 951268 792172 748100
922790 262573 363596 34883
755556 714487 234743 610394
413603 489527 114329 351936
409240 356171 378350 234973
300813 97383 263307 49846
579258 900270 84403 704902
563965 876076 387516 770189
36896 156893 23161 1...

output:

YES
158639 154150
YES
32971 42393
YES
472763 478507
NO
YES
95178 89311
YES
103401 128709
YES
231155 178086
YES
252122 48692
YES
82752 136254
YES
281983 594094
YES
18449 138446
YES
36507 35593
YES
14951 31328
YES
332452 120181
YES
95890 92352
YES
1360 9003
NO
YES
463012 112498
YES
320245 320244
YES
1...

result:

wrong answer wrong solution, (966991 in base 320245) != (646748 in base 320244) (test case 19)