#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
const int NM = 2e5, inf = 1e9+7;
namespace advisor{
int col[NM+5], lst[NM+5], nxt[NM+5];
bool ok[NM+5];
priority_queue <pii> q;
bool ans[NM+5];
void solve(int *C, int N, int K, int M){
assert(M > 0);
for (int i = 0; i < K; i++) col[i] = i;
for (int i = 0; i < N; i++) col[K+i] = C[i];
for (int i = 0; i < N; i++) lst[i] = -1;
for (int i = N+K-1; i >= 0; i--){
if (lst[col[i]] == -1) nxt[i] = +inf;
else nxt[i] = lst[col[i]];
lst[col[i]] = i;
}
for (int i = 0; i < K; i++) q.push(mp(+inf+1, -1));
for (int i = 0; i < N+K; i++){
if (ok[col[i]]){
q.push(mp(nxt[i], i));
continue;
}
pii P = q.top(); q.pop();
if (P.se != -1){
ans[P.se] = 1;
ok[col[P.se]] = 0;
}
q.push(mp(nxt[i], i));
ok[col[i]] = 1;
}
for (int i = 0; i < N+K; i++) WriteAdvice(ans[i]);
}
}
void ComputeAdvice(int *C, int N, int K, int M){
advisor::solve(C, N, K, M);
}
#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
const int NM = 2e5, inf = 1e9+7;
namespace assistant{
queue <int> q;
bool ok[NM+5];
void solve(unsigned char *A, int N, int K, int R){
assert(R == N+K);
for (int i = 0; i < K; i++){
ok[i] = 1;
if (A[i]) q.push(i);
}
for (int i = 0; i < N; i++){
int x = GetRequest();
if (!ok[x]){
int y = q.front(); q.pop();
PutBack(y);
ok[y] = 0;
ok[x] = 1;
}
if (A[K+i]) q.push(x);
}
}
}
void Assist(unsigned char *A, int N, int K, int R){
assistant::solve(A, N, K, R);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2844 KB |
Output is correct |
2 |
Correct |
1 ms |
2844 KB |
Output is correct |
3 |
Correct |
2 ms |
2840 KB |
Output is correct |
4 |
Correct |
2 ms |
2848 KB |
Output is correct |
5 |
Correct |
3 ms |
2872 KB |
Output is correct |
6 |
Correct |
3 ms |
2872 KB |
Output is correct |
7 |
Correct |
3 ms |
3136 KB |
Output is correct |
8 |
Correct |
3 ms |
2880 KB |
Output is correct |
9 |
Correct |
3 ms |
2872 KB |
Output is correct |
10 |
Correct |
3 ms |
3636 KB |
Output is correct |
11 |
Correct |
3 ms |
2876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
3176 KB |
Output is correct |
2 |
Correct |
22 ms |
4860 KB |
Output is correct |
3 |
Correct |
49 ms |
6836 KB |
Output is correct |
4 |
Correct |
50 ms |
5912 KB |
Output is correct |
5 |
Correct |
41 ms |
6188 KB |
Output is correct |
6 |
Correct |
44 ms |
6528 KB |
Output is correct |
7 |
Correct |
47 ms |
6908 KB |
Output is correct |
8 |
Correct |
40 ms |
6104 KB |
Output is correct |
9 |
Correct |
38 ms |
6424 KB |
Output is correct |
10 |
Correct |
49 ms |
7084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
5924 KB |
Output is correct |
2 |
Correct |
50 ms |
7256 KB |
Output is correct |
3 |
Correct |
48 ms |
7276 KB |
Output is correct |
4 |
Correct |
48 ms |
7376 KB |
Output is correct |
5 |
Correct |
47 ms |
7168 KB |
Output is correct |
6 |
Correct |
47 ms |
7160 KB |
Output is correct |
7 |
Correct |
47 ms |
6840 KB |
Output is correct |
8 |
Correct |
48 ms |
6768 KB |
Output is correct |
9 |
Correct |
45 ms |
7008 KB |
Output is correct |
10 |
Correct |
49 ms |
6872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2872 KB |
Output is correct |
2 |
Correct |
3 ms |
3020 KB |
Output is correct |
3 |
Correct |
3 ms |
2876 KB |
Output is correct |
4 |
Correct |
3 ms |
2876 KB |
Output is correct |
5 |
Correct |
3 ms |
2880 KB |
Output is correct |
6 |
Correct |
3 ms |
2968 KB |
Output is correct |
7 |
Correct |
3 ms |
2872 KB |
Output is correct |
8 |
Correct |
4 ms |
2880 KB |
Output is correct |
9 |
Correct |
3 ms |
2864 KB |
Output is correct |
10 |
Correct |
4 ms |
3136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
6876 KB |
Output is correct - 120000 bits used |
2 |
Correct |
52 ms |
6764 KB |
Output is correct - 122000 bits used |
3 |
Correct |
50 ms |
6652 KB |
Output is correct - 125000 bits used |
4 |
Correct |
48 ms |
6868 KB |
Output is correct - 125000 bits used |
5 |
Correct |
49 ms |
6644 KB |
Output is correct - 125000 bits used |
6 |
Correct |
47 ms |
6864 KB |
Output is correct - 125000 bits used |
7 |
Correct |
52 ms |
6996 KB |
Output is correct - 124828 bits used |
8 |
Correct |
53 ms |
6908 KB |
Output is correct - 124910 bits used |
9 |
Correct |
47 ms |
6876 KB |
Output is correct - 125000 bits used |
10 |
Correct |
46 ms |
6608 KB |
Output is correct - 125000 bits used |