QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#20997#2492. Hash FunctionMacesutedWA 14ms3712kbC++144.2kb2022-02-23 16:32:012022-05-03 12:11:20

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:11:20]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:3712kb
  • [2022-02-23 16:32:01]
  • 提交

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

int n;
long long maxS;
vector<int> S1, S2, S3;
map<long long, long long> record;

long long get(int p, int n) { return (1LL << p) | ((p & 1) ? (1LL << (p >> 1)) : (1LL << (2 * n - 1 - (p >> 1)))); }
long long R(long long S) { return (S >> 1) | ((S & 1) << (2 * n - 1)); }
long long calcB(long long A) {
    long long B = 0;
    for (int t = 0; t < n; t++) B |= ((A >> t & 1) ^ (A >> (2 * t + 1) & 1)) << t;
    for (int t = n; t < 2 * n; t++) B |= ((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>(), mod = (1LL << (2 * n - 1)) - 1;
    maxS = (1LL << (2 * n)) - 1;
    long long max1S = ((1LL << n) - 1) << n, max2S = (1LL << n) - 1;
    for (int i = 0; i < 2 * n; i++) {
        long long S = get(i, n);
        S = S ^ R(S);
        vector<int> pos;
        for (int j = 0; j < 2 * n; j++)
            if (S >> 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 << S3z); i++) {
        long long A_ = 0;
        for (int t = 0; t < S3z; t++) A_ |= (i >> t & 1) << S3[t];
        for (int j = 0; j < (1 << S1z); j++) {
            long long A = A_;
            for (int t = 0; t < S1z; t++) A |= (j >> t & 1) << S1[t];
            long long B = calcB(A), C = B ^ R(B);
            A &= max1S, C &= max1S;
            record[(H + mod - (239 * A + 153 * C) % mod) % mod] = A;
        }
        for (int j = 0; j < (1 << S2z); j++) {
            long long A = A_;
            for (int t = 0; t < S2z; t++) A |= (j >> t & 1) << S2[t];
            long long B = calcB(A), C = B ^ R(B);
            A &= max2S, C &= max2S;
            auto p = record.find((239 * A + 153 * C) % mod);
            if (p != record.end()) return write(p->second | A), putch('\n');
        }
        record.clear();
    }
    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: 1ms
memory: 3700kb

input:

4 83

output:

112

result:

ok good solution

Test #2:

score: -100
Wrong Answer
time: 14ms
memory: 3712kb

input:

10 497091

output:

No Solution!

result:

wrong output format Expected integer, but "No" found