QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#704749 | #6519. X Equals Y | lllei# | WA | 702ms | 6632kb | C++20 | 3.0kb | 2024-11-02 20:54:08 | 2024-11-02 20:54:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int bas = 1333331;
int T;
map<int, int> mp;
pair<int, int> pii;
bool check(int l1, int r1, int l2, int r2, int d)
{
// cout<<l1<<' '<<r1<<' '<<l2<<' '<<r2<<endl;
if (l1 % d != l2 % d)
return false;
if (r1 < l2 || l1 > r2)
return false;
if (l2 <= l1 && l1 <= r2)
{
pii = {0, (l1 - l2) / d};
return true;
}
if (l2 <= r1 && r1 <= r2)
{
pii = {(r1 - l1) / d, (r1 - l2) / d};
return true;
}
if (l1 <= l2 && l2 <= r1)
{
pii = {(l2 - l1) / d, 0};
return true;
}
if (l1 <= r2 && r2 <= r1)
{
pii = {(r2 - l1) / d, (r2 - l2) / d};
return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> T;
while (T--)
{
mp.clear();
int x, y, A, B, flg = 0;
cin >> x >> y >> A >> B;
int lim = sqrt(max(x, y));
for (int i = 2; i <= min(lim + 1, A); i++)
{
int cur = 0, t = x;
vector<int> num;
while (t)
{
num.push_back(t % i);
t = t / i;
}
reverse(num.begin(), num.end());
for (auto cc : num)
cur = (cur * 1LL * bas + cc) % mod;
mp[cur] = i;
}
for (int i = 2; i <= min(lim + 1, B); i++)
{
int cur = 0, t = y;
vector<int> num;
while (t)
{
num.push_back(t % i);
t = t / i;
}
reverse(num.begin(), num.end());
for (auto cc : num)
cur = (cur * 1LL * bas + cc) % mod;
if (mp[cur])
{
cout << "YES\n";
cout << mp[cur] << ' ' << i << '\n';
flg = 1;
break;
}
}
if (flg)
continue;
if (x == y && A > x && B > y)
{
cout << "YES\n";
cout << x + 1 << ' ' << y + 1 << '\n';
continue;
}
A = min(x, A);
B = min(y, B);
// cout << A << ' ' << B << endl;
int tt=max(x/A,y/B);
for (int l1 = min(x/tt,A), l2 = min(y/tt, B), r1, r2; l1 >= 1 && l2 >= 1; l1 = r1 - 1, l2 = r2 - 1)
{
if (x / l1 >= l1)
break;
if (y / l2 >= l2)
break;
r1 = x / (x / l1 + 1) + 1;
r2 = y / (y / l2 + 1) + 1;
// cout << x / l1<<' '<<y/l2 << endl;
// cout<<l1<<' '<<l2<<endl;
if (check(x % l1, x % r1, y % l2, y % r2, x / l1))
{
cout << "YES\n";
cout << l1 - pii.first << ' ' << l2 - pii.second << '\n';
flg = 1;
break;
}
}
if (!flg)
cout << "NO\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
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 3 11 YES 4 5 NO YES 6 10
result:
ok correct (6 test cases)
Test #2:
score: 0
Accepted
time: 3ms
memory: 3516kb
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 756 497 YES 17 151 NO YES 289 291 NO YES 86 75 YES 25 10 NO YES 341 413 NO NO NO NO YES 415 145 YES 107 84 YES 15 188 NO NO YES 47 39 YES 12 249 NO NO YES 16 5 YES 151 120 NO YES 750 346 NO YES 67 196 NO YES 66 29 NO NO YES 94 54 YES 6 5 NO NO NO NO NO YES 324 129 NO YES 237 224 YES 17 25 YES 28...
result:
ok correct (1000 test cases)
Test #3:
score: 0
Accepted
time: 240ms
memory: 3832kb
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 235254 230765 YES 37680 47102 YES 472763 478507 NO YES 107936 102069 YES 467 521 YES 288042 234973 YES 253276 49846 YES 84403 137905 YES 387516 699627 YES 139 338 YES 40881 39967 YES 16611 32988 YES 344148 131877 YES 713 699 YES 1381 9024 NO YES 536175 185661 YES 138141 92392 YES 109907 782369 Y...
result:
ok correct (1000 test cases)
Test #4:
score: -100
Wrong Answer
time: 702ms
memory: 6632kb
input:
1000 981241785 906230829 601363803 626653490 197057696 698550046 128696358 449956015 182548925 796382933 101642956 339324198 816288818 177783961 308532802 32376477 628394197 777548138 355072973 757299936 599075146 752655475 473746059 323396924 261214299 95047810 181049121 60329182 7484303 329571035 ...
output:
YES 23170 23082 YES 7140 13806 YES 2644 481 YES 11612 5330 YES 11019 12059 YES 25023 15274 YES 10528 6353 YES 2685 16669 YES 1796495 1768498 YES 2335 2446 YES 18219 17340 YES 23225 30 YES 9529 25632 YES 20848 20964 YES 9371 11368 YES 16778 6486 YES 12005 5889 YES 13362 12047 YES 8141 11971 YES 19972...
result:
wrong answer wrong solution, (981241785 in base 23170) != (906230829 in base 23082) (test case 1)