QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226389#7322. Random NumbersPPP#RE 696ms8472kbC++172.4kb2023-10-25 22:04:232023-10-25 22:04:23

Judging History

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

  • [2023-10-25 22:04:23]
  • 评测
  • 测评结果:RE
  • 用时:696ms
  • 内存:8472kb
  • [2023-10-25 22:04:23]
  • 提交

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...

output:


result: