QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#491289 | #2806. Mona Lisa | arnold518 | AC ✓ | 502ms | 249460kb | C++14 | 3.1kb | 2024-07-25 18:29:40 | 2024-07-25 18:29:42 |
Judging History
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);
}
Details
Tip: Click on the bar to expand more detailed information
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