QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#21016 | #2492. Hash Function | _silhouette_ | Compile Error | / | / | C++14 | 4.9kb | 2022-02-24 08:10:00 | 2022-05-18 04:10:39 |
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-18 04:10:39]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2022-02-24 08:10:00]
- 提交
answer
* @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
class Hashlist {
private:
static const int MOD = 114514;
struct Node {
long long key, val;
int nxt;
};
Node heap[MOD+5];
int cnt;
int list[MOD];
int cache[1<<26], ccnt = 0;
int newNode(void) { return ++cnt; }
public:
Hashlist() {
cnt = 0;
for (int i = 0; i < MOD; i++) list[i] = 0;
return;
}
void clear(void) {
for (int i = 0; i < ccnt; i++) list[cache[i]] = 0;
return cnt = ccnt = 0, void();
}
void insert(long long key, long long val) {
int x = key % MOD, p = newNode();
if (!list[x]) cache[ccnt++] = x;
heap[p].key = key, heap[p].val = val, heap[p].nxt = list[x], list[x] = p;
return;
}
long long ask(long long key) {
int p = list[key % MOD];
while (p) {
if (heap[p].key == key) return heap[p].val;
p = heap[p].nxt;
}
return -1;
}
} ha;
int n;
long long maxS, mod;
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++) {
long long S = calcB(1LL << i);
S = S ^ R(S);
if (!S) continue;
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_ |= (long long)(i >> t & 1) << S3[t];
for (int j = 0; j < (1 << S2z); j++) {
long long A = A_;
for (int t = 0; t < S2z; t++) A |= (long long)(j >> t & 1) << S2[t];
long long B = calcB(A), C = (B ^ R(B)) & max2S;
ha.insert((H + mod - (239 * A + 153 * C) % mod) % mod, A);
}
for (int j = 0; j < (1 << S1z); j++) {
long long A = 0;
for (int t = 0; t < S1z; t++) A |= (long long)(j >> t & 1) << S1[t];
long long B = calcB(A | A_), C = (B ^ R(B)) & max1S;
auto p = ha.ask((239 * A + 153 * C) % mod);
if (p != -1) return write(p | A), putch('\n');
}
ha.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
answer.code:1:4: error: stray ‘@’ in program 1 | * @copyright Copyright (c) 2022 | ^ answer.code:2:4: error: stray ‘@’ in program 2 | * @brief | ^ answer.code:1:15: error: expected constructor, destructor, or type conversion before ‘Copyright’ 1 | * @copyright Copyright (c) 2022 | ^~~~~~~~~ In file included from /usr/include/c++/11/cmath:43, from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41, from answer.code:7: /usr/include/c++/11/ext/type_traits.h:162:35: error: ‘bool __gnu_cxx::__is_null_pointer’ redeclared as different kind of entity 162 | __is_null_pointer(std::nullptr_t) | ^ /usr/include/c++/11/ext/type_traits.h:157:5: note: previous declaration ‘template<class _Type> bool __gnu_cxx::__is_null_pointer(_Type)’ 157 | __is_null_pointer(_Type) | ^~~~~~~~~~~~~~~~~ /usr/include/c++/11/ext/type_traits.h:162:26: error: ‘nullptr_t’ is not a member of ‘std’ 162 | __is_null_pointer(std::nullptr_t) | ^~~~~~~~~ In file included from /usr/include/c++/11/bits/exception_ptr.h:40, from /usr/include/c++/11/exception:147, from /usr/include/c++/11/ios:39, from /usr/include/c++/11/istream:38, from /usr/include/c++/11/sstream:38, from /usr/include/c++/11/complex:45, from /usr/include/c++/11/ccomplex:39, from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54, from answer.code:7: /usr/include/c++/11/new:126:26: error: declaration of ‘operator new’ as non-function 126 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc) | ^~~~~~~~ /usr/include/c++/11/new:126:44: error: ‘size_t’ is not a member of ‘std’; did you mean ‘time_t’? 126 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc) | ^~~~~~ | time_t /usr/include/c++/11/new:127:41: error: attributes after parenthesized initializer ignored [-fpermissive] 127 | __attribute__((__externally_visible__)); | ^ /usr/include/c++/11/new:128:26: error: declaration of ‘operator new []’ as non-function 128 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc) | ^~~~~~~~ /usr/include/c++/11/new:128:46: error: ‘size_t’ is not a member of ‘std’; did you mean ‘time_t’? 128 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc) | ^~~~~~ | time_t /usr/include/c++/11/new:129:41: error: attributes after parenthesized initializer ignored [-fpermissive] 129 | __attribute__((__externally_visible__)); | ^ /usr/include/c++/11/new:135:34: error: ‘std::size_t’ has not been declared 135 | void operator delete(void*, std::size_t) _GLIBCXX_USE_NOEXCEPT | ^~~~~~ /usr/include/c++/11/new:137:36: error: ‘std::size_t’ has not been declared 137 | void operator delete[](void*, std::size_t) _GLIBCXX_USE_NOEXCEPT | ^~~~~~ /usr/include/c++/11/new:140:26: error: declaration of ‘operator new’ as non-function 140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT | ^~~~~~~~ /usr/include/c++/11/new:140:44: error: ‘size_t’ is not a member of ‘std’; did you mean ‘time_t’? 140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT | ^~~~~~ | time_t /usr/include/c++/11/new:140:52: error: expected primary-expression before ‘const’ 140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT | ^~~~~ /usr/include/c++/11/new:142:26: error: declaration of ‘operator new []’ as non-function 142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT | ^~~~~~~~ /usr/include/c++/11/new:142:46: error: ‘size_t’ is not a member of ‘std’; did you mean ‘time_t’? 142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT | ^~~~~~ | time_t /usr/include/c++/11/new:142:54: error: expected primary-expression before ‘const’ 142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLI...