#include "advisor.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define float long double
#define elif else if
#define endl "\n"
#define mod 1000000007
#define pi acos(-1)
#define eps 0.000000001
#define inf 1000'000'000'000'000'000LL
#define FIXED(a) cout << fixed << setprecision(a)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define time_init auto start = std::chrono::high_resolution_clock::now()
#define time_report \
auto end = std::chrono::high_resolution_clock::now(); \
std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << endl
#define debug(x) \
{ cerr << #x << " = " << x << endl; }
#define len(x) (int) x.size()
#define sqr(x) ((x) * (x))
#define cube(x) ((x) * (x) * (x))
#define bit(x, i) (((x) >> (i)) & 1)
#define set_bit(x, i) ((x) | (1LL << (i)))
#define clear_bit(x, i) ((x) & (~(1LL << (i))))
#define toggle_bit(x, i) ((x) ^ (1LL << (i)))
#define low_bit(x) ((x) & (-(x)))
#define count_bit(x) __builtin_popcountll(x)
#define srt(x) sort(all(x))
#define rsrt(x) sort(rall(x))
#define mp make_pair
#define maxel(x) (*max_element(all(x)))
#define minel(x) (*min_element(all(x)))
#define maxelpos(x) (max_element(all(x)) - x.begin())
#define minelpos(x) (min_element(all(x)) - x.begin())
#define sum(x) (accumulate(all(x), 0LL))
#define product(x) (accumulate(all(x), 1LL, multiplies<int>()))
#define gcd __gcd
#define lcm(a, b) ((a) / gcd(a, b) * (b))
#define rev(x) (reverse(all(x)))
#define shift_left(x, k) (rotate(x.begin(), x.begin() + k, x.end()))
#define shift_right(x, k) (rotate(x.rbegin(), x.rbegin() + k, x.rend()))
#define is_sorted(x) (is_sorted_until(all(x)) == x.end())
#define is_even(x) (((x) &1) == 0)
#define is_odd(x) (((x) &1) == 1)
#define pow2(x) (1LL << (x))
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using matrix = vector<vector<T>>;
template<typename T>
using graph = vector<vector<T>>;
using hashmap = gp_hash_table<int, int, custom_hash>;
template<typename T>
vector<T> vect(int n, T val) {
return vector<T>(n, val);
}
template<typename T>
vector<vector<T>> vect(int n, int m, T val) {
return vector<vector<T>>(n, vector<T>(m, val));
}
template<typename T>
vector<vector<vector<T>>> vect(int n, int m, int k, T val) {
return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, val)));
}
template<typename T>
vector<vector<vector<vector<T>>>> vect(int n, int m, int k, int l, T val) {
return vector<vector<vector<vector<T>>>>(n, vector<vector<vector<T>>>(m, vector<vector<T>>(k, vector<T>(l, val))));
}
template<typename T>
matrix<T> new_matrix(int n, int m, T val) {
return matrix<T>(n, vector<T>(m, val));
}
template<typename T>
graph<T> new_graph(int n) {
return graph<T>(n);
}
template<class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template<class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;
using i128 = __int128_t;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;
template<typename T>
using vec = vector<T>;
using pII = pair<int, int>;
template<typename T>
using enumerated = pair<T, int>;
template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
os << "(" << p.first << ", " << p.second << ")";
return os;
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
os << "{";
for (int i = 0; i < v.size(); ++i) {
if (i) os << ", ";
os << v[i];
}
os << "}";
return os;
}
template<typename T>
ostream &operator<<(ostream &os, const set<T> &v) {
os << "[";
for (auto it = v.begin(); it != v.end(); ++it) {
if (it != v.begin()) os << ", ";
os << *it;
}
os << "]";
return os;
}
template<typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &v) {
os << "[";
for (auto it = v.begin(); it != v.end(); ++it) {
if (it != v.begin()) os << ", ";
os << it->first << " = " << it->second;
}
os << "]";
return os;
}
void ComputeAdvice(i32 *C, i32 N, i32 K, i32 M) {
auto encode = [&](int x) {
for (int i = 17; i >= 0; i--) {
WriteAdvice((x >> i) & 1);
}
};
vec<int> c(C, C + N);
for (int i = 0; i < N; i++) {
encode(C[i]);
}
}
#include "assistant.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define float long double
#define elif else if
#define endl "\n"
#define mod 1000000007
#define pi acos(-1)
#define eps 0.000000001
#define inf 1000'000'000'000'000'000LL
#define FIXED(a) cout << fixed << setprecision(a)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define time_init auto start = std::chrono::high_resolution_clock::now()
#define time_report \
auto end = std::chrono::high_resolution_clock::now(); \
std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << endl
#define debug(x) \
{ cerr << #x << " = " << x << endl; }
#define len(x) (int) x.size()
#define sqr(x) ((x) * (x))
#define cube(x) ((x) * (x) * (x))
#define bit(x, i) (((x) >> (i)) & 1)
#define set_bit(x, i) ((x) | (1LL << (i)))
#define clear_bit(x, i) ((x) & (~(1LL << (i))))
#define toggle_bit(x, i) ((x) ^ (1LL << (i)))
#define low_bit(x) ((x) & (-(x)))
#define count_bit(x) __builtin_popcountll(x)
#define srt(x) sort(all(x))
#define rsrt(x) sort(rall(x))
#define mp make_pair
#define maxel(x) (*max_element(all(x)))
#define minel(x) (*min_element(all(x)))
#define maxelpos(x) (max_element(all(x)) - x.begin())
#define minelpos(x) (min_element(all(x)) - x.begin())
#define sum(x) (accumulate(all(x), 0LL))
#define product(x) (accumulate(all(x), 1LL, multiplies<int>()))
#define gcd __gcd
#define lcm(a, b) ((a) / gcd(a, b) * (b))
#define rev(x) (reverse(all(x)))
#define shift_left(x, k) (rotate(x.begin(), x.begin() + k, x.end()))
#define shift_right(x, k) (rotate(x.rbegin(), x.rbegin() + k, x.rend()))
#define is_sorted(x) (is_sorted_until(all(x)) == x.end())
#define is_even(x) (((x) &1) == 0)
#define is_odd(x) (((x) &1) == 1)
#define pow2(x) (1LL << (x))
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using matrix = vector<vector<T>>;
template<typename T>
using graph = vector<vector<T>>;
using hashmap = gp_hash_table<int, int, custom_hash>;
template<typename T>
vector<T> vect(int n, T val) {
return vector<T>(n, val);
}
template<typename T>
vector<vector<T>> vect(int n, int m, T val) {
return vector<vector<T>>(n, vector<T>(m, val));
}
template<typename T>
vector<vector<vector<T>>> vect(int n, int m, int k, T val) {
return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, val)));
}
template<typename T>
vector<vector<vector<vector<T>>>> vect(int n, int m, int k, int l, T val) {
return vector<vector<vector<vector<T>>>>(n, vector<vector<vector<T>>>(m, vector<vector<T>>(k, vector<T>(l, val))));
}
template<typename T>
matrix<T> new_matrix(int n, int m, T val) {
return matrix<T>(n, vector<T>(m, val));
}
template<typename T>
graph<T> new_graph(int n) {
return graph<T>(n);
}
template<class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template<class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;
using i128 = __int128_t;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;
template<typename T>
using vec = vector<T>;
using pII = pair<int, int>;
template<typename T>
using enumerated = pair<T, int>;
void Assist(unsigned char *A, i32 n, i32 k, i32 R) {
vec<bool> a(R);
for (int i{}; i < R; ++i) a[i] = A[i];
vec<int> c;
for (int i = 0; i < R; i += 18) {
int mask = 0;
for (int j = i; j < i + 18; j++) {
mask = mask * 2 + a[j];
}
c.push_back(mask);
}
map<int, queue<int>> pos;
for (int i = 0; i < n; i++) {
pos[c[i]].push(i);
}
set<pair<int, int>> cur;
auto next_occ = [&](int x) {
if (pos[x].empty()) return inf;
return pos[x].front();
};
for (int i = 0; i < k; i++) {
cur.insert({next_occ(i), i});
}
int cnt = 0;
for (int i = 0; i < n; i++) {
int r = GetRequest();
if (cur.count({next_occ(r), r})) {
cur.erase({next_occ(r), r});
pos[r].pop();
cur.insert({next_occ(r), r});
continue;
}
// for (int s: cur) {
// int t = 0;
// if (pos.count(s) == 0 or pos[s].empty())
// t = inf;
// else {
// t = pos[s].front();
// }
// if (t > next_t) {
// next_t = t;
// best = s;
// }
// }
auto [t, best] = *cur.rbegin();
PutBack(best);
cnt++;
cur.erase({t, best});
pos[r].pop();
cur.insert({next_occ(r), r});
}
if(cnt > k + n/k + 10) while(true);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
784 KB |
Output is correct |
| 2 |
Correct |
0 ms |
784 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1580 KB |
Output is correct |
| 4 |
Execution timed out |
2502 ms |
1316 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2596 ms |
7384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2518 ms |
55620 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
800 KB |
Error - advice is too long |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2523 ms |
67780 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2522 ms |
68516 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2581 ms |
69244 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2553 ms |
69320 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2559 ms |
69312 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2566 ms |
69280 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2548 ms |
69564 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2572 ms |
69312 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2558 ms |
69312 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2551 ms |
87996 KB |
Time limit exceeded |
