#include <bits/stdc++.h>
#include "advisor.h"
#define F first
#define S second
using namespace std;
const int N = 1e5 + 10;
int n , m , k , ar[N] , lg;
vector <int> pos[N];
bool marked[N];
struct SEG{
int sum[N << 2];
void Add(int x , int node = 1 , int nl = 0 , int nr = n)
{
sum[node]++;
if(nl + 1 == nr)
return;
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(x < mid)
Add(x , lc , nl , mid);
else
Add(x , rc , mid , nr);
}
void Rem(int x , int node = 1 , int nl = 0 , int nr = n)
{
sum[node]--;
if(nl + 1 == nr)
return;
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(x < mid)
Rem(x , lc , nl , mid);
else
Rem(x , rc , mid , nr);
}
int Get_val(int x , int node = 1 , int nl = 0 , int nr = n)
{
if(nl + 1 == nr)
return nl;
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(x <= sum[lc])
return Get_val(x , lc , nl , mid);
else
return Get_val(x - sum[lc] , rc , mid , nr);
}
int Get_id(int x , int node = 1 , int nl = 0 , int nr = n)
{
if(nl + 1 == nr)
return sum[node];
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(x < mid)
return Get_id(x , lc , nl , mid);
else
return sum[lc] + Get_id(x , rc , mid , nr);
}
bool Ex(int x , int node = 1 , int nl = 0 , int nr = n)
{
if(nl + 1 == nr)
return sum[node];
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(x < mid)
return Ex(x , lc , nl , mid);
else
return Ex(x , rc , mid , nr);
}
} seg;
void Print(int val)
{
for(int i = 0 ; i < lg ; i++)
{
if((val >> i) & 1)
WriteAdvice(1);
else
WriteAdvice(0);
}
}
void ComputeAdvice(int *C, int nn, int kk, int mm) {
n = nn;
k = kk;
m = mm;
lg = 1;
int tmp = 2;
while(tmp < k)
{
lg++;
tmp *= 2;
}
for(int i = 0 ; i < n ; i++)
{
ar[i] = C[i];
pos[i].push_back(n + 1);
}
for(int i = n - 1 ; i > -1 ; i--)
{
pos[ar[i]].push_back(i);
}
set <pair<int , int>> st;
vector <int> vec;
for(int i = 0 ; i < k ; i++)
{
seg.Add(i);
st.insert(make_pair(pos[i].back() , i));
}
for(int i = 0 ; i < k ; i++)
{
if(pos[i].size() == 1)
{
marked[i] = true;
vec.push_back(i);
WriteAdvice(1);
}
else
WriteAdvice(0);
}
for(int i = k ; i < n ; i++)
{
if(pos[i].size() == 2)
{
marked[i] = true;
WriteAdvice(1);
}
else
WriteAdvice(0);
}
for(int i = 0 ; i < n ; i++)
{
if(!seg.Ex(ar[i]))
{
pos[ar[i]].pop_back();
auto it = st.end(); it--; auto now = *it;
if(!vec.empty())
{
now = make_pair(n + 1 , vec.back());
vec.pop_back();
st.erase(now);
seg.Rem(now.S);
seg.Add(ar[i]);
st.insert(make_pair(pos[ar[i]].back() , ar[i]));
if(marked[ar[i]])
vec.push_back(ar[i]);
continue;
}
st.erase(now);
int id_rem = seg.Get_id(now.S);
id_rem--;
seg.Rem(now.S);
seg.Add(ar[i]);
st.insert(make_pair(pos[ar[i]].back() , ar[i]));
Print(id_rem);
}
else
{
st.erase(make_pair(pos[ar[i]].back() , ar[i]));
pos[ar[i]].pop_back();
st.insert(make_pair(pos[ar[i]].back() , ar[i]));
}
}
}
//
#include <bits/stdc++.h>
#include "assistant.h"
#define F first
#define S second
using namespace std;
const int N = 1e5 + 10;
int n2 , k2 , r2 , lg2;
struct SEG{
int sum[N << 2];
void Add(int x , int node = 1 , int nl = 0 , int nr = n2)
{
sum[node]++;
if(nl + 1 == nr)
return;
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(x < mid)
Add(x , lc , nl , mid);
else
Add(x , rc , mid , nr);
}
void Rem(int x , int node = 1 , int nl = 0 , int nr = n2)
{
sum[node]--;
if(nl + 1 == nr)
return;
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(x < mid)
Rem(x , lc , nl , mid);
else
Rem(x , rc , mid , nr);
}
int Get_val(int x , int node = 1 , int nl = 0 , int nr = n2)
{
if(nl + 1 == nr)
return nl;
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(x <= sum[lc])
return Get_val(x , lc , nl , mid);
else
return Get_val(x - sum[lc] , rc , mid , nr);
}
int Get_id(int x , int node = 1 , int nl = 0 , int nr = n2)
{
if(nl + 1 == nr)
return sum[node];
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(x < mid)
return Get_id(x , lc , nl , mid);
else
return sum[lc] + Get_id(x , rc , mid , nr);
}
bool Ex(int x , int node = 1 , int nl = 0 , int nr = n2)
{
if(nl + 1 == nr)
return sum[node];
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(x < mid)
return Ex(x , lc , nl , mid);
else
return Ex(x , rc , mid , nr);
}
} seg2;
void Assist(unsigned char *ar, int nn, int kk, int rr) {
n2 = nn;
k2 = kk;
r2 = rr;
lg2 = 1;
int tmp = 2;
while(tmp < k2)
{
lg2++;
tmp *= 2;
}
//cout << lg2 << endl;
vector <int> vec;
for(int i = 0 ; i < k2 ; i++)
{
seg2.Add(i);
if(ar[i] == 1)
vec.push_back(i);
}
int pos = n2;
for(int i = 0 ; i < n2 ; i++)
{
int now = GetRequest();
if(seg2.Ex(now))
continue;
if(!vec.empty())
{
int bd = vec.back();
PutBack(bd);
seg2.Rem(bd);
seg2.Add(now);
vec.pop_back();
if(ar[now])
vec.push_back(now);
continue;
}
int id = 0;
for(int j = 0 ; j < lg2 ; j++)
{
if(ar[pos] == 1)
{
id |= (1 << j);
}
pos++;
}
id++;
int bd = seg2.Get_val(id);
PutBack(bd);
seg2.Rem(bd);
seg2.Add(now);
if(ar[now])
vec.push_back(now);
}
}
//
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3112 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3100 KB |
Output isn't correct - not an optimal way |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
4592 KB |
Output isn't correct - not an optimal way |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
128 ms |
14636 KB |
Output isn't correct - not an optimal way |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3376 KB |
Error - advice is too long |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
168 ms |
17204 KB |
Output isn't correct - not an optimal way |
| 2 |
Incorrect |
196 ms |
16940 KB |
Output isn't correct - not an optimal way |
| 3 |
Incorrect |
167 ms |
16904 KB |
Output isn't correct - not an optimal way |
| 4 |
Incorrect |
163 ms |
16796 KB |
Output isn't correct - not an optimal way |
| 5 |
Incorrect |
159 ms |
16936 KB |
Output isn't correct - not an optimal way |
| 6 |
Incorrect |
158 ms |
16780 KB |
Output isn't correct - not an optimal way |
| 7 |
Incorrect |
160 ms |
16752 KB |
Output isn't correct - not an optimal way |
| 8 |
Incorrect |
165 ms |
16580 KB |
Output isn't correct - not an optimal way |
| 9 |
Incorrect |
158 ms |
16796 KB |
Output isn't correct - not an optimal way |
| 10 |
Incorrect |
226 ms |
20192 KB |
Output isn't correct - not an optimal way |
