QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21018#2492. Hash FunctionMacesutedAC ✓1375ms11916kbC++145.1kb2022-02-24 08:19:042022-05-03 12:18:45

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-03 12:18:45]
  • 评测
  • 测评结果:AC
  • 用时:1375ms
  • 内存:11916kb
  • [2022-02-24 08:19:04]
  • 提交

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