#include "advisor.h"
#include <iostream>
#include <utility>
#include <cassert>
#include <set>
#include <deque>
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
const int maxN = 1e5 + 326;
bool has[maxN];
set<pii> st;
deque<int> dq[maxN];
void ComputeAdvice(int *C, int N, int K, int M) {
fill(has, has + K, 1);
for(int i = 0; i < N; i++){
dq[C[i]].push_back(i);
}
for(int i = 0; i < K; i++){
int furt = dq[i].size() ? dq[i].front() : maxN;
st.insert({furt, i});
}
int bitcount = 0;
while((1 << bitcount) < N + 1) bitcount++;
for(int i = 0; i < N; i++){ //thirteen bits lol
int key;
if(has[C[i]]) key = (1 << bitcount) - 1;
else {
pii nc = *st.rbegin();
st.erase(st.find(nc));
has[nc.S] = false;
has[C[i]] = true;
key = nc.S;
while(dq[C[i]].size() && dq[C[i]].front() <= i) dq[C[i]].pop_front();
int furt = dq[C[i]].size() ? dq[C[i]].front() : maxN;
st.insert({furt, C[i]});
}
int furt = dq[C[i]].size() ? dq[C[i]].front() : maxN;
st.erase(st.find({furt, C[i]}));
while(dq[C[i]].size() && dq[C[i]].front() <= i) dq[C[i]].pop_front();
furt = dq[C[i]].size() ? dq[C[i]].front() : maxN;
st.insert({furt, C[i]});
for(int j = 0; j < bitcount; j++){
WriteAdvice((key >> j) & 1);
}
}
}
#include "assistant.h"
void Assist(unsigned char *A, int N, int K, int R) {
int bitcount = 0;
while((1 << bitcount) < N + 1) bitcount++;
for(int i = 0; i < N; i++){
int req = GetRequest();
int key = 0;
for(int j = (i + 1) * bitcount - 1; j >= (i) * bitcount; j--){
key = key * 2 + A[j];
}
if(key != (1 << bitcount) - 1) PutBack(key);
}
}
Compilation message
assistant.cpp: In function 'void Assist(unsigned char*, int, int, int)':
assistant.cpp:8:7: warning: unused variable 'req' [-Wunused-variable]
8 | int req = GetRequest();
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
68480 KB |
Output is correct |
2 |
Correct |
55 ms |
68632 KB |
Output is correct |
3 |
Correct |
56 ms |
68348 KB |
Output is correct |
4 |
Correct |
63 ms |
68560 KB |
Output is correct |
5 |
Correct |
72 ms |
68576 KB |
Output is correct |
6 |
Correct |
72 ms |
68604 KB |
Output is correct |
7 |
Correct |
70 ms |
68752 KB |
Output is correct |
8 |
Correct |
71 ms |
69112 KB |
Output is correct |
9 |
Correct |
71 ms |
68604 KB |
Output is correct |
10 |
Correct |
73 ms |
68940 KB |
Output is correct |
11 |
Correct |
70 ms |
68732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
92 ms |
69476 KB |
Output is correct |
2 |
Correct |
281 ms |
74636 KB |
Output is correct |
3 |
Correct |
542 ms |
82356 KB |
Output is correct |
4 |
Correct |
508 ms |
80508 KB |
Output is correct |
5 |
Correct |
535 ms |
80652 KB |
Output is correct |
6 |
Correct |
516 ms |
80924 KB |
Output is correct |
7 |
Correct |
542 ms |
81420 KB |
Output is correct |
8 |
Correct |
473 ms |
79992 KB |
Output is correct |
9 |
Correct |
489 ms |
80256 KB |
Output is correct |
10 |
Correct |
538 ms |
81932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
438 ms |
79636 KB |
Output is correct |
2 |
Incorrect |
147 ms |
71688 KB |
Error - advice is too long |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
55 ms |
68676 KB |
Error - advice is too long |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
550 ms |
81708 KB |
Output is partially correct - 1700000 bits used |
2 |
Correct |
532 ms |
81824 KB |
Output is partially correct - 1700000 bits used |
3 |
Correct |
558 ms |
82028 KB |
Output is partially correct - 1700000 bits used |
4 |
Correct |
544 ms |
82048 KB |
Output is partially correct - 1700000 bits used |
5 |
Correct |
538 ms |
81724 KB |
Output is partially correct - 1700000 bits used |
6 |
Correct |
562 ms |
81796 KB |
Output is partially correct - 1700000 bits used |
7 |
Correct |
542 ms |
81796 KB |
Output is partially correct - 1697263 bits used |
8 |
Correct |
542 ms |
81936 KB |
Output is partially correct - 1700000 bits used |
9 |
Correct |
546 ms |
81944 KB |
Output is partially correct - 1700000 bits used |
10 |
Correct |
530 ms |
82124 KB |
Output is partially correct - 1700000 bits used |