QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#429133 | #6519. X Equals Y | dnialh# | WA | 295ms | 3748kb | C++20 | 6.3kb | 2024-06-02 01:18:45 | 2024-06-02 01:18:45 |
Judging History
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)