#include "advisor.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pp pop_back
#define sz(x) (int)x.size()
#define rep(z, a, b) for (int z = (a); (z) <= (b); z++)
#define per(z, a, b) for (int z = (a); (z) >= (b); z--)
using namespace std;
const int MAXN = (int)2e5 + 7;
struct tree {
int t[MAXN << 2];
void upd(int p, int x, int v = 1, int tl = 0, int tr = MAXN) {
if (tl == tr) {
t[v] += x;
return;
}
int tm = tl + tr >> 1;
if (p <= tm) upd(p, x, v << 1, tl, tm);
else upd(p, x, v << 1 | 1, tm +1 , tr);
t[v] = t[v << 1] + t[v << 1 | 1];
}
int get(int l, int r, int v = 1, int tl = 0, int tr = MAXN) {
if (l <= tl && tr <= r) return t[v];
if (tl > r || tr < l) return 0;
int tm = tl + tr >> 1;
return get(l, r, v << 1, tl, tm) + get(l, r, v << 1 | 1, tm + 1, tr);
}
int kth(int x, int v = 1, int tl = 0, int tr = MAXN) {
if (tl == tr) return tl;
int tm = tl + tr >> 1;
if (t[v << 1] >= x) return kth(x, v << 1, tl, tm);
return kth(x - t[v << 1], v << 1 | 1, tm + 1, tr);
}
} f;
vector <int> nxt[MAXN];
set <int> in;
set < pair <int, int > > dp;
void ComputeAdvice(int *C, int N, int K, int M) {
rep(i, 0, N - 1) {
nxt[i].pb(N);
}
per(i, N - 1, 0) {
nxt[C[i]].pb(i);
}
rep(i, 0, K - 1) {
in.insert(i);
dp.insert({nxt[i].back(), i});
f.upd(i, 1);
}
int LOG = log2(K);
rep(i, 0, N - 1) {
if (in.count(C[i])) {
continue;
}
while (sz(dp) && dp.begin() -> f <= i) {
int x = dp.begin() -> s;
dp.erase(dp.begin());
nxt[x].pp();
dp.insert({nxt[x].back(), x});
}
int del = dp.rbegin() -> s, id = f.get(0, del) - 1;
dp.erase(--dp.end());
in.erase(del);
in.insert(C[i]);
f.upd(C[i], 1);
f.upd(del, -1);
dp.insert({nxt[C[i]].back(), C[i]});
// cerr << "PUT -> " << del << endl;
rep(j, 0, LOG) {
if (id & (1 << j)) WriteAdvice(1);
else WriteAdvice(0);
}
}
}
#include "assistant.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pp pop_back
#define sz(x) (int)x.size()
#define rep(z, a, b) for (int z = (a); (z) <= (b); z++)
#define per(z, a, b) for (int z = (a); (z) >= (b); z--)
using namespace std;
const int MAXN = (int)2e5 + 7;
struct fenwick {
int t[MAXN << 2];
void upd(int p, int x, int v = 1, int tl = 0, int tr = MAXN) {
if (tl == tr) {
t[v] += x;
return;
}
int tm = tl + tr >> 1;
if (p <= tm) upd(p, x, v << 1, tl, tm);
else upd(p, x, v << 1 | 1, tm +1 , tr);
t[v] = t[v << 1] + t[v << 1 | 1];
}
int kth(int x, int v = 1, int tl = 0, int tr = MAXN) {
if (tl == tr) return tl;
int tm = tl + tr >> 1;
if (t[v << 1] >= x) return kth(x, v << 1, tl, tm);
return kth(x - t[v << 1], v << 1 | 1, tm + 1, tr);
}
} T;
void Assist(unsigned char *A, int N, int K, int R) {
int LOG = log2(K);
set <int> st;
rep(i, 0, K - 1) {
st.insert(i);
T.upd(i, 1);
}
int i = 0;
for (int z = 0; z < N; z++) {
int add = GetRequest();
if (st.count(add)) {
i++;
continue;
}
else {
int id = 0;
rep(j, 0, LOG) {
if (A[i + j] == 1) id |= 1 << j;
}
int val = T.kth(id + 1);
i += LOG + 1;
// cerr << val << " -> " << endl;
PutBack(val);
T.upd(val, -1);
st.erase(val);
}
st.insert(add);
T.upd(add, 1);
}
}
Compilation message
advisor.cpp: In member function 'void tree::upd(int, int, int, int, int)':
advisor.cpp:27:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int tm = tl + tr >> 1;
~~~^~~~
advisor.cpp: In member function 'int tree::get(int, int, int, int, int)':
advisor.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int tm = tl + tr >> 1;
~~~^~~~
advisor.cpp: In member function 'int tree::kth(int, int, int, int)':
advisor.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int tm = tl + tr >> 1;
~~~^~~~
assistant.cpp: In member function 'void fenwick::upd(int, int, int, int, int)':
assistant.cpp:26:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int tm = tl + tr >> 1;
~~~^~~~
assistant.cpp: In member function 'int fenwick::kth(int, int, int, int)':
assistant.cpp:33:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int tm = tl + tr >> 1;
~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
10224 KB |
Output isn't correct - not an optimal way |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
12016 KB |
Error - Putting back a color that is not on the scaffold |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
293 ms |
25584 KB |
Error - Putting back a color that is not on the scaffold |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
10736 KB |
Error - advice is too long |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
390 ms |
29048 KB |
Error - Putting back a color that is not on the scaffold |
| 2 |
Incorrect |
376 ms |
29176 KB |
Error - Putting back a color that is not on the scaffold |
| 3 |
Incorrect |
373 ms |
29936 KB |
Error - Putting back a color that is not on the scaffold |
| 4 |
Incorrect |
376 ms |
29464 KB |
Error - Putting back a color that is not on the scaffold |
| 5 |
Incorrect |
380 ms |
29968 KB |
Error - Putting back a color that is not on the scaffold |
| 6 |
Incorrect |
378 ms |
29680 KB |
Error - Putting back a color that is not on the scaffold |
| 7 |
Incorrect |
377 ms |
29640 KB |
Error - Putting back a color that is not on the scaffold |
| 8 |
Incorrect |
376 ms |
29680 KB |
Error - Putting back a color that is not on the scaffold |
| 9 |
Incorrect |
381 ms |
29776 KB |
Error - Putting back a color that is not on the scaffold |
| 10 |
Incorrect |
458 ms |
31736 KB |
Error - Putting back a color that is not on the scaffold |
