QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#491292#2806. Mona Lisaarnold518AC ✓511ms231520kbC++142.9kb2024-07-25 18:30:352024-07-25 18:30:36

Judging History

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

  • [2024-07-25 18:30:36]
  • 评测
  • 测评结果:AC
  • 用时:511ms
  • 内存:231520kb
  • [2024-07-25 18:30:35]
  • 提交

answer

#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
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)
{
    typedef unsigned long long uint64;
    uint64 state[2] = { seed, seed ^ 0x7263d9bd8409f526 };
    for(int i = 0; i < SZ; ++i)
    {
        uint64 s0 = state[0];
        uint64 s1 = state[1];
        uint64 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); }

int 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;

    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, -1, -1 });
            if(it != X.end() && (*it)[0] == tar)
            {
                cout << (*it)[1] + 1 << ' ' << (*it)[2] + 1 << ' ' << j + 1 << ' ' << k + 1;
                return 0;
            }
        }
    }

    assert(false);
}

详细

Test #1:

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

input:

50
3641603982383516983 445363681616962640 868196408185819179 1980241222855773941

output:

669802 263331 255904 500556

result:

ok mask = 17081027486709448704

Test #2:

score: 0
Accepted
time: 480ms
memory: 230652kb

input:

50
3055145645388798701 4084695091667323991 8393866115111650437 8276211103020686332

output:

326601 1021480 504920 346697

result:

ok mask = 4726527808925335552

Test #3:

score: 0
Accepted
time: 477ms
memory: 230112kb

input:

50
4447187206772987967 5057003807331015529 3683646399867750937 4959929340524289631

output:

1037609 657199 390394 466288

result:

ok mask = 13734852963573170176

Test #4:

score: 0
Accepted
time: 482ms
memory: 231240kb

input:

30
4447187206772987967 5057003807331015529 3683646399867750937 4959929340524289631

output:

1037609 657199 390394 466288

result:

ok mask = 13734852963573170176

Test #5:

score: 0
Accepted
time: 481ms
memory: 231520kb

input:

40
2000553641426646242 8394266588800462858 5174813619441966549 5380082235969655544

output:

249939 278486 134117 72331

result:

ok mask = 7990511638862102528

Test #6:

score: 0
Accepted
time: 480ms
memory: 229812kb

input:

30
8971595278382332609 8797766056660025197 8814581332485447937 7913323398633635457

output:

902138 769823 903010 665900

result:

ok mask = 1402871283925909504

Test #7:

score: 0
Accepted
time: 477ms
memory: 231480kb

input:

20
7655154655267048263 5690015887455518604 7298309383797106776 5385921941394025776

output:

77482 312640 953009 377047

result:

ok mask = 17337732665469566976

Test #8:

score: 0
Accepted
time: 511ms
memory: 230224kb

input:

10
2907715170862079926 4383657789263533416 3441315991803441580 6710361405732069162

output:

623910 158849 356742 677319

result:

ok mask = 7983756239421046784

Test #9:

score: 0
Accepted
time: 490ms
memory: 230440kb

input:

1
1844356018046553200 908939614249024770 297739836703096371 991031776856734449

output:

478869 659735 60120 527384

result:

ok mask = 13299129699625074688