QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#226389 | #7322. Random Numbers | PPP# | RE | 696ms | 8472kb | C++17 | 2.4kb | 2023-10-25 22:04:23 | 2023-10-25 22:04:23 |
Judging History
answer
//#ifdef DEBUG
//#define _GLIBCXX_DEBUG
//#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef long double ld;
int n;
const int maxN = 2e5 + 10;
ll a[maxN];
ll b[maxN];
ll extGcd(ll a, ll b, ll& x, ll& y) {
if (a == 0) {
x = 0, y = 1;
return b;
}
ll x1, y1;
ll g = extGcd(b % a, a, x1, y1);
x = y1 - (b / a) * x1;
y = x1;
return g;
}
ll c[maxN];
bool check(ll m, ll k) {
for (int i = 0; i < n; i++) c[i] = (a[i] + k) % m;
sort(c, c + n);
for (int i = 0; i < n; i++) {
if (c[i] != b[i]) return false;
}
return true;
}
mt19937_64 rnd(228);
const ll M = 1e18;
void solve() {
__int128 S = 0;
// n = 1e5;
for (int i = 0; i < n; i++) {
cin >> a[i];
// a[i] = rnd() % M;
S += a[i];
}
ll Sb = 0;
for (int i = 0; i < n; i++) {
cin >> b[i];
// b[i] = (a[i] + 141414141) % 3939329323;
Sb += b[i];
}
sort(b, b + n);
ll mx = *max_element(b, b + n) + 1;
// cout << mx << " ? " << 3939329323 - mx << endl;
for (ll m = mx; ; m++) {
// cout << m << " CHECK " << endl;
// if (m == 3939329323) {
// cout << " YSE " << endl;
// }
__int128 F = Sb - S;
F %= m;
ll X = F;
if (X < 0) X += m;
ll D = __gcd((ll)n, m);
if (X % D != 0) continue;
ll md = m / D;
ll xd = X / D;
assert(xd < md);
ll x, y;
extGcd(n, md, x, y);
x %= md;
if (x < 0) x += md;
assert((n * x - 1) % md == 0);
ll pk = (__int128(X) * x) % md;
for (ll K = pk; K < m; K += md) {
bool ok = true;
for (int i = 0; i < n; i++) {
int ps = lower_bound(b, b + n, (a[i] + K) % m) - b;
if (ps != n && b[ps] == (a[i] + K) % m) {
}
else {
ok = false;
break;
}
}
if (ok && check(m, K)) {
cout << m << " " << K << '\n';
return;
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef DEBUG
freopen("input.txt", "r", stdin);
#endif
while (cin >> n) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 696ms
memory: 8008kb
input:
100000 567521362129079894 696655062397105489 618592056868108007 305121979898345388 418241613626143516 566981041096909436 687040795047811890 413478956193714535 294233239559482609 517064297715474906 919243760085177084 146712184879435114 334896924897329674 808181231522418580 201231480069623536 26529430...
output:
100 67
result:
ok ok
Test #2:
score: 0
Accepted
time: 81ms
memory: 8472kb
input:
200000 279519034965658533 597593214175301180 791322407400185163 578922257802743818 414641183084379116 322797787270966916 290473958850416021 68048123764088964 295440872117700499 53885977901037256 884227817550465910 435454695330542508 543950240412210545 861061959631272210 610282134233366541 8147478322...
output:
9551360648 6883666787
result:
ok ok
Test #3:
score: -100
Runtime Error
input:
200000 167774018375528485 714562772221376663 198818958454505969 581190629893484837 438687470464075495 790572767580670700 710940444599804113 650871502364047098 596477567071759597 702504178760375793 74780058995621376 382060312959449666 943533333637489584 152035322602398106 387034388851610387 579808941...