QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#21018 | #2492. Hash Function | Macesuted | AC ✓ | 1375ms | 11916kb | C++14 | 5.1kb | 2022-02-24 08:19:04 | 2022-05-03 12:18:45 |
Judging History
answer
/**
* @file 2492.cpp
* @author Macesuted ([email protected])
* @date 2022-02-23
*
* @copyright Copyright (c) 2022
* @brief
* Time Limit: 3S Memory Limit: 64M
*
*/
#include <bits/stdc++.h>
using namespace std;
#define MP make_pair
#define MT make_tuple
namespace io {
#define SIZE (1 << 20)
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
int f, qr;
inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
inline char getch(void) {
return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
}
void putch(char x) {
*oS++ = x;
if (oS == oT) flush();
return;
}
string getstr(void) {
string s = "";
char c = getch();
while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch();
return s;
}
void putstr(string str, int begin = 0, int end = -1) {
if (end == -1) end = str.size();
for (int i = begin; i < end; i++) putch(str[i]);
return;
}
template <typename T>
T read() {
T x = 0;
for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
return x * f;
}
template <typename T>
void write(const T& t) {
T x = t;
if (!x) putch('0');
if (x < 0) putch('-'), x = -x;
while (x) qu[++qr] = x % 10 + '0', x /= 10;
while (qr) putch(qu[qr--]);
return;
}
struct Flusher_ {
~Flusher_() { flush(); }
} io_flusher_;
} // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;
bool mem1;
#define maxn 17
#define MOD 1145
class Hashlist {
private:
struct Node {
long long key, val;
int nxt;
};
Node heap[1005];
public:
int list[MOD], cnt;
Hashlist() {
cnt = 0;
for (int i = 0; i < MOD; i++) list[i] = 0;
return;
}
void insert(long long key, long long val) {
int x = key % MOD;
heap[++cnt].key = key, heap[cnt].val = val, heap[cnt].nxt = list[x], list[x] = cnt;
return;
}
long long ask(long long key) {
for (register int p = list[key % MOD]; p; p = heap[p].nxt)
if (heap[p].key == key) return heap[p].val;
return -1;
}
} ha;
int n;
long long maxS, mod, rec[105], X[maxn * 2], vS1[1 << 7], vS2[1 << 7], vS3[1 << 19], vC1[1 << 7], vC2[1 << 7], vC3[1 << 19];
vector<int> S1, S2, S3;
long long R(long long S) { return (S >> 1) | ((long long)(S & 1) << (2 * n - 1)); }
long long calcB(long long A) {
long long B = 0;
for (int t = 0; t < n; t++) B |= (long long)((A >> t & 1) ^ (A >> (2 * t + 1) & 1)) << t;
for (int t = n; t < 2 * n; t++) B |= (long long)((A >> t & 1) ^ (A >> (4 * n - 2 * t - 2) & 1)) << t;
return B;
}
void solve(void) {
n = read<int>();
long long H = read<long long>(), max1S = (1LL << n) - 1, max2S = max1S << n;
maxS = (1LL << (2 * n)) - 1, mod = (1LL << (2 * n - 1)) - 1;
for (int i = 0; i < 2 * n; i++) {
X[i] = calcB(1LL << i);
X[i] = X[i] ^ R(X[i]);
if (!X[i]) continue;
vector<int> pos;
for (int j = 0; j < 2 * n; j++)
if (X[i] >> j & 1) pos.push_back(j);
if (pos.back() < n)
S1.push_back(i);
else if (pos.front() >= n)
S2.push_back(i);
else
S3.push_back(i);
}
int S1z = S1.size(), S2z = S2.size(), S3z = S3.size();
for (int i = 0; i < (1 << S1z); i++) {
vS1[i] = 0;
for (int t = 0; t < S1z; t++)
if (i >> t & 1) vS1[i] |= 1LL << S1[t], vC1[i] ^= X[S1[t]];
}
for (int i = 0; i < (1 << S2z); i++) {
vS2[i] = 0;
for (int t = 0; t < S2z; t++)
if (i >> t & 1) vS2[i] |= 1LL << S2[t], vC2[i] ^= X[S2[t]];
}
for (int i = 0; i < (1 << S3z); i++) {
vS3[i] = 0;
for (int t = 0; t < S3z; t++)
if (i >> t & 1) vS3[i] |= 1LL << S3[t], vC3[i] ^= X[S3[t]];
}
for (int i = 0; i < (1 << S3z); i++) {
for (int j = 0; j < (1 << S2z); j++) {
long long A = vS3[i] | vS2[j], C = (vC2[j] ^ vC3[i]) & max2S;
ha.insert(rec[j] = (H + mod - (239LL * A + 153LL * C) % mod) % mod, A);
}
for (int j = 0; j < (1 << S1z); j++) {
long long A = vS1[j], C = (vC1[j] ^ vC3[i]) & max1S;
auto p = ha.ask((239 * A + 153 * C) % mod);
if (p != -1) return write(p | A), putch('\n');
}
for (int j = 0; j < (1 << S2z); j++) ha.list[rec[j] % MOD] = 0;
ha.cnt = 0;
}
return putstr("No Solution!\n");
}
bool mem2;
int main() {
#ifdef MACESUTED
cerr << "Memory: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
#endif
int _ = 1;
while (_--) solve();
#ifdef MACESUTED
cerr << "Time: " << clock() * 1000. / CLOCKS_PER_SEC << "ms" << endl;
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3676kb
input:
4 83
output:
13
result:
ok good solution
Test #2:
score: 0
Accepted
time: 3ms
memory: 3700kb
input:
10 497091
output:
153014
result:
ok good solution
Test #3:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
4 55
output:
73
result:
ok good solution
Test #4:
score: 0
Accepted
time: 200ms
memory: 7700kb
input:
15 444650548
output:
377677832
result:
ok good solution
Test #5:
score: 0
Accepted
time: 62ms
memory: 5596kb
input:
14 114355996
output:
119238393
result:
ok good solution
Test #6:
score: 0
Accepted
time: 34ms
memory: 11916kb
input:
16 0
output:
0
result:
ok good solution
Test #7:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
3 22
output:
8
result:
ok good solution
Test #8:
score: 0
Accepted
time: 3ms
memory: 3756kb
input:
8 8319
output:
47842
result:
ok good solution
Test #9:
score: 0
Accepted
time: 19ms
memory: 4136kb
input:
12 7629490
output:
11766463
result:
ok good solution
Test #10:
score: 0
Accepted
time: 3ms
memory: 3676kb
input:
2 2
output:
3
result:
ok good solution
Test #11:
score: 0
Accepted
time: 26ms
memory: 11764kb
input:
16 0
output:
0
result:
ok good solution
Test #12:
score: 0
Accepted
time: 30ms
memory: 11708kb
input:
16 0
output:
0
result:
ok good solution
Test #13:
score: 0
Accepted
time: 30ms
memory: 11908kb
input:
16 0
output:
0
result:
ok good solution
Test #14:
score: 0
Accepted
time: 6ms
memory: 3928kb
input:
11 1086647
output:
1875946
result:
ok good solution
Test #15:
score: 0
Accepted
time: 1ms
memory: 3928kb
input:
11 188671
output:
393405
result:
ok good solution
Test #16:
score: 0
Accepted
time: 7ms
memory: 3896kb
input:
11 2028522
output:
3482225
result:
ok good solution
Test #17:
score: 0
Accepted
time: 46ms
memory: 4556kb
input:
13 23601796
output:
40518521
result:
ok good solution
Test #18:
score: 0
Accepted
time: 3ms
memory: 3560kb
input:
8 29405
output:
39139
result:
ok good solution
Test #19:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
7 2218
output:
3174
result:
ok good solution
Test #20:
score: 0
Accepted
time: 3ms
memory: 3676kb
input:
7 432
output:
662
result:
ok good solution
Test #21:
score: 0
Accepted
time: 2ms
memory: 3916kb
input:
11 899191
output:
570326
result:
ok good solution
Test #22:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
5 494
output:
281
result:
ok good solution
Test #23:
score: 0
Accepted
time: 2ms
memory: 3656kb
input:
8 13862
output:
51543
result:
ok good solution
Test #24:
score: 0
Accepted
time: 4ms
memory: 3788kb
input:
11 899027
output:
3346232
result:
ok good solution
Test #25:
score: 0
Accepted
time: 3ms
memory: 3708kb
input:
8 7446
output:
49853
result:
ok good solution
Test #26:
score: 0
Accepted
time: 3ms
memory: 3576kb
input:
3 12
output:
6
result:
ok good solution
Test #27:
score: 0
Accepted
time: 3ms
memory: 3580kb
input:
8 6258
output:
18666
result:
ok good solution
Test #28:
score: 0
Accepted
time: 248ms
memory: 7732kb
input:
15 191474555
output:
411455767
result:
ok good solution
Test #29:
score: 0
Accepted
time: 2ms
memory: 3728kb
input:
3 17
output:
20
result:
ok good solution
Test #30:
score: 0
Accepted
time: 210ms
memory: 7644kb
input:
15 161474861
output:
318717104
result:
ok good solution
Test #31:
score: 0
Accepted
time: 3ms
memory: 3844kb
input:
10 180816
output:
81147
result:
ok good solution
Test #32:
score: 0
Accepted
time: 3ms
memory: 3516kb
input:
4 116
output:
81
result:
ok good solution
Test #33:
score: 0
Accepted
time: 229ms
memory: 11900kb
input:
16 1196684556
output:
567748713
result:
ok good solution
Test #34:
score: 0
Accepted
time: 165ms
memory: 11784kb
input:
16 1087033358
output:
458416341
result:
ok good solution
Test #35:
score: 0
Accepted
time: 534ms
memory: 11736kb
input:
16 2112546660
output:
1321210677
result:
ok good solution
Test #36:
score: 0
Accepted
time: 1185ms
memory: 11912kb
input:
16 130507716
output:
3358127644
result:
ok good solution
Test #37:
score: 0
Accepted
time: 376ms
memory: 11736kb
input:
16 1531459999
output:
1004811660
result:
ok good solution
Test #38:
score: 0
Accepted
time: 414ms
memory: 11736kb
input:
16 1905706077
output:
1437054237
result:
ok good solution
Test #39:
score: 0
Accepted
time: 870ms
memory: 11784kb
input:
16 1584950777
output:
2565491169
result:
ok good solution
Test #40:
score: 0
Accepted
time: 110ms
memory: 11760kb
input:
16 1112585098
output:
312451907
result:
ok good solution
Test #41:
score: 0
Accepted
time: 528ms
memory: 11812kb
input:
16 1527899944
output:
1488817943
result:
ok good solution
Test #42:
score: 0
Accepted
time: 1069ms
memory: 11916kb
input:
16 1234237908
output:
3150139837
result:
ok good solution
Test #43:
score: 0
Accepted
time: 175ms
memory: 11848kb
input:
16 922629865
output:
237178966
result:
ok good solution
Test #44:
score: 0
Accepted
time: 1375ms
memory: 11784kb
input:
16 2079610945
output:
4169495274
result:
ok good solution
Test #45:
score: 0
Accepted
time: 684ms
memory: 11832kb
input:
16 125431469
output:
2028551108
result:
ok good solution
Test #46:
score: 0
Accepted
time: 717ms
memory: 11820kb
input:
16 425515915
output:
1873120589
result:
ok good solution
Test #47:
score: 0
Accepted
time: 209ms
memory: 11828kb
input:
16 882748949
output:
873576051
result:
ok good solution
Test #48:
score: 0
Accepted
time: 116ms
memory: 11788kb
input:
16 1647578253
output:
45770769
result:
ok good solution
Test #49:
score: 0
Accepted
time: 922ms
memory: 11708kb
input:
16 1687169193
output:
3025007262
result:
ok good solution
Test #50:
score: 0
Accepted
time: 752ms
memory: 11732kb
input:
16 702542621
output:
2485649646
result:
ok good solution