QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#491289#2806. Mona Lisaarnold518AC ✓502ms249460kbC++143.1kb2024-07-25 18:29:402024-07-25 18:29:42

Judging History

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

  • [2024-07-25 18:29:42]
  • 评测
  • 测评结果:AC
  • 用时:502ms
  • 内存:249460kb
  • [2024-07-25 18:29:40]
  • 提交

answer

#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
#define int unsigned long long
typedef unsigned long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef array<int, 3> tiii;

const int SZ = 1 << 20;
ll A[SZ];
ll B[SZ];
ll C[SZ];
ll D[SZ];
vector<int> lA[SZ];
vector<int> lB[SZ];
vector<int> lC[SZ];
vector<int> lD[SZ];

void f(unsigned long long seed, ll *arr)
{
    ull state[2] = { seed, seed ^ 0x7263d9bd8409f526 };
    for(int i = 0; i < SZ; ++i)
    {
        ull s0 = state[0];
        ull s1 = state[1];
        ull result = s0 + s1;
        s1 ^= s0;
        state[0] = ((s0 << 55) | (s0 >> 9)) ^ s1 ^ (s1 << 14);
        state[1] = (s1 << 36) | (s1 >> 28);
        arr[i] = ll(result & ((1ull << 50) - 1));
    }
}

mt19937 rnd(1557);
int rng(int l, int r) { return uniform_int_distribution<int>(l, r)(rnd); }

signed main() 
{
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    int n; cin >> n;
    unsigned long long a, b, c, d; cin >> a >> b >> c >> d;
    
    f(a, A);
    f(b, B);
    f(c, C);
    f(d, D);
    // for(int i = 0; i < 20; ++i) cout << A[i] << ' '; cout << endl;
    // for(int i = 0; i < 20; ++i) cout << B[i] << ' '; cout << endl;
    // for(int i = 0; i < 20; ++i) cout << C[i] << ' '; cout << endl;
    // for(int i = 0; i < 20; ++i) cout << D[i] << ' '; cout << endl;
    // cout << (A[286] ^ B[17608] ^ C[122885] ^ D[59913]) << endl;

    int N = SZ;
    ll msk = (1 << 20) - 1;
    for(int i = 0; i < N; ++i) lA[A[i] & msk].push_back(i);
    for(int i = 0; i < N; ++i) lB[B[i] & msk].push_back(i);
    for(int i = 0; i < N; ++i) lC[C[i] & msk].push_back(i);
    for(int i = 0; i < N; ++i) lD[D[i] & msk].push_back(i);

    int x;
    while(1)
    {
        x = rng(0, (1 << 20) - 1);

        ll a = 0, b = 0;
        for(int i = 0; i < N; ++i) a += (ll)lA[i].size() * (ll)lB[i ^ x].size();
        for(int i = 0; i < N; ++i) b += (ll)lC[i].size() * (ll)lD[i ^ x].size();
        // cout << a << ' ' << b << endl;
        if(a > (ll)3e5 && b > (ll)3e5) break;
    }

    vector<tiii> X;
    for(int i = 0; i < N; ++i)
    {
        for(int j : lA[i])
        {
            for(int k : lB[i ^ x])
            {
                assert(((A[j] ^ B[k]) & msk) == x);
                X.push_back({ (int)((A[j] ^ B[k]) >> 20), j, k });
                if(X.size() >= SZ) break;
            }
            if(X.size() >= SZ) break;
        }
        if(X.size() >= SZ) break;
    }

    sort(X.begin(), X.end());

    for(int i = 0; i < N; ++i)
    {
        for(int j : lC[i]) for(int k : lD[i ^ x])
        {
            int tar = (C[j] ^ D[k]) >> 20;
            auto it = lower_bound(X.begin(), X.end(), tiii{ tar, 0, 0 });
            if(it != X.end() && (*it)[0] == tar)
            {
                assert((A[(*it)[1]] ^ B[(*it)[2]] ^ C[j] ^ D[k]) == 0);
                cout << (*it)[1] + 1 << ' ' << (*it)[2] + 1 << ' ' << j + 1 << ' ' << k + 1 << '\n';
                return 0;
            }
        }
    }

    assert(false);
}

详细

Test #1:

score: 100
Accepted
time: 486ms
memory: 248640kb

input:

50
3641603982383516983 445363681616962640 868196408185819179 1980241222855773941

output:

669802 263331 255904 500556

result:

ok mask = 17081027486709448704

Test #2:

score: 0
Accepted
time: 485ms
memory: 249460kb

input:

50
3055145645388798701 4084695091667323991 8393866115111650437 8276211103020686332

output:

326601 1021480 504920 346697

result:

ok mask = 4726527808925335552

Test #3:

score: 0
Accepted
time: 502ms
memory: 247604kb

input:

50
4447187206772987967 5057003807331015529 3683646399867750937 4959929340524289631

output:

1037609 657199 390394 466288

result:

ok mask = 13734852963573170176

Test #4:

score: 0
Accepted
time: 489ms
memory: 247560kb

input:

30
4447187206772987967 5057003807331015529 3683646399867750937 4959929340524289631

output:

1037609 657199 390394 466288

result:

ok mask = 13734852963573170176

Test #5:

score: 0
Accepted
time: 486ms
memory: 249280kb

input:

40
2000553641426646242 8394266588800462858 5174813619441966549 5380082235969655544

output:

249939 278486 134117 72331

result:

ok mask = 7990511638862102528

Test #6:

score: 0
Accepted
time: 491ms
memory: 248492kb

input:

30
8971595278382332609 8797766056660025197 8814581332485447937 7913323398633635457

output:

902138 769823 903010 665900

result:

ok mask = 1402871283925909504

Test #7:

score: 0
Accepted
time: 487ms
memory: 247480kb

input:

20
7655154655267048263 5690015887455518604 7298309383797106776 5385921941394025776

output:

77482 312640 953009 377047

result:

ok mask = 17337732665469566976

Test #8:

score: 0
Accepted
time: 496ms
memory: 248928kb

input:

10
2907715170862079926 4383657789263533416 3441315991803441580 6710361405732069162

output:

623910 158849 356742 677319

result:

ok mask = 7983756239421046784

Test #9:

score: 0
Accepted
time: 484ms
memory: 247512kb

input:

1
1844356018046553200 908939614249024770 297739836703096371 991031776856734449

output:

478869 659735 60120 527384

result:

ok mask = 13299129699625074688