#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];
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++)
WriteAdvice(((val >> i) & 1));
}
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;
for(int i = 0 ; i < k ; i++)
{
seg.Add(i);
st.insert(make_pair(pos[i].back() , i));
}
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;
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;
}
for(int i = 0 ; i < k2 ; i++)
seg2.Add(i);
int pos = 0;
for(int i = 0 ; i < n2 ; i++)
{
int now = GetRequest();
if(seg2.Ex(now))
continue;
int id = 0;
for(int i = 0 ; i < lg2 ; i++)
{
if(ar[pos] == '1')
id |= (1 << i);
pos++;
}
id++;
int bd = seg2.Get_val(id);
PutBack(bd);
seg2.Rem(bd);
seg2.Add(now);
}
}
//
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4888 KB |
Output is correct |
2 |
Incorrect |
1 ms |
4892 KB |
Output isn't correct - not an optimal way |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
13 ms |
6080 KB |
Output isn't correct - not an optimal way |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
128 ms |
16664 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
5128 KB |
Error - advice is too long |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
163 ms |
19208 KB |
Execution killed with signal 11 |
2 |
Runtime error |
161 ms |
19152 KB |
Execution killed with signal 11 |
3 |
Runtime error |
161 ms |
19104 KB |
Execution killed with signal 11 |
4 |
Runtime error |
158 ms |
19036 KB |
Execution killed with signal 11 |
5 |
Runtime error |
148 ms |
19084 KB |
Execution killed with signal 11 |
6 |
Runtime error |
168 ms |
19172 KB |
Execution killed with signal 11 |
7 |
Runtime error |
161 ms |
19004 KB |
Execution killed with signal 11 |
8 |
Runtime error |
162 ms |
19092 KB |
Execution killed with signal 11 |
9 |
Runtime error |
159 ms |
19008 KB |
Execution killed with signal 11 |
10 |
Runtime error |
208 ms |
21712 KB |
Execution killed with signal 11 |