#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
#include "advisor.h"
queue<int> use[MX];
int nex[MX], res;
set<pi> nexUse;
set<int> del[MX], USE[MX], cur;
/*unsigned char* A = new unsigned char[100];
int z = 0;
void WriteAdvice(int x) {
A[z++] = x;
cout << x << "\n";
}*/
int cat(int col, int ti) {
auto it0 = USE[col].ub(ti);
auto it1 = del[col].ub(ti);
if (it0 == USE[col].end()) return 0;
if (it1 == del[col].end()) return 1;
return *it0 < *it1;
}
void ComputeAdvice(int *C, int N, int K, int M) {
F0R(i,N) use[C[i]].push(i);
F0R(i,N) { nex[i] = MOD; if (sz(use[i])) nex[i] = use[i].front(); }
F0R(i,K) { cur.insert(i); nexUse.insert({nex[i],i}); }
F0R(i,N) {
USE[C[i]].insert(i);
if (cur.find(C[i]) == cur.end()) {
auto a = *nexUse.rbegin();
cur.erase(a.s); nexUse.erase(a);
del[a.s].insert(i);
cur.insert(C[i]); nexUse.insert({nex[C[i]],C[i]});
}
nexUse.erase({nex[C[i]],C[i]});
use[C[i]].pop();
if (sz(use[C[i]])) nex[C[i]] = use[C[i]].front();
else nex[C[i]] = MOD;
nexUse.insert({nex[C[i]],C[i]});
}
F0R(i,K) WriteAdvice(cat(i,-1));
F0R(i,N) WriteAdvice(cat(C[i],i));
}
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
#include "assistant.h"
/*int C[4] = {2,0,3,0};
int IND = 0;
int GetRequest() {
return C[IND++];
}
void PutBack(int x) {
cout << "BAD " << x << "\n";
}*/
int ind = 0;
int getNex(unsigned char *A) { return A[ind++]; }
set<int> canDelete, S;
void Assist(unsigned char *A, int N, int K, int R) {
F0R(i,K) {
int x = getNex(A);
if (!x) canDelete.insert(i);
S.insert(i);
}
F0R(i,N) {
int req = GetRequest();
if (S.find(req) == S.end()) {
int x = *canDelete.begin();
PutBack(x); canDelete.erase(x); S.erase(x);
S.insert(req);
}
if (!getNex(A)) canDelete.insert(req);
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
90 ms |
154096 KB |
Output is correct |
2 |
Correct |
75 ms |
154576 KB |
Output is correct |
3 |
Correct |
97 ms |
154936 KB |
Output is correct |
4 |
Correct |
89 ms |
155456 KB |
Output is correct |
5 |
Correct |
83 ms |
156032 KB |
Output is correct |
6 |
Correct |
82 ms |
156032 KB |
Output is correct |
7 |
Correct |
83 ms |
156032 KB |
Output is correct |
8 |
Correct |
84 ms |
156408 KB |
Output is correct |
9 |
Correct |
94 ms |
156408 KB |
Output is correct |
10 |
Correct |
94 ms |
156624 KB |
Output is correct |
11 |
Correct |
96 ms |
156624 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
100 ms |
157872 KB |
Output is correct |
2 |
Correct |
206 ms |
165208 KB |
Output is correct |
3 |
Correct |
487 ms |
182088 KB |
Output is correct |
4 |
Correct |
320 ms |
182088 KB |
Output is correct |
5 |
Correct |
379 ms |
182088 KB |
Output is correct |
6 |
Correct |
401 ms |
182088 KB |
Output is correct |
7 |
Correct |
436 ms |
183112 KB |
Output is correct |
8 |
Correct |
361 ms |
183984 KB |
Output is correct |
9 |
Correct |
340 ms |
185088 KB |
Output is correct |
10 |
Correct |
503 ms |
187904 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
369 ms |
187904 KB |
Output is correct |
2 |
Correct |
633 ms |
188968 KB |
Output is correct |
3 |
Correct |
480 ms |
190696 KB |
Output is correct |
4 |
Correct |
461 ms |
190832 KB |
Output is correct |
5 |
Correct |
417 ms |
190832 KB |
Output is correct |
6 |
Correct |
486 ms |
193888 KB |
Output is correct |
7 |
Correct |
583 ms |
194528 KB |
Output is correct |
8 |
Correct |
433 ms |
198696 KB |
Output is correct |
9 |
Correct |
384 ms |
198696 KB |
Output is correct |
10 |
Correct |
499 ms |
198696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
107 ms |
198696 KB |
Output is correct |
2 |
Correct |
84 ms |
198696 KB |
Output is correct |
3 |
Correct |
87 ms |
198696 KB |
Output is correct |
4 |
Correct |
81 ms |
198696 KB |
Output is correct |
5 |
Correct |
93 ms |
198696 KB |
Output is correct |
6 |
Correct |
82 ms |
198696 KB |
Output is correct |
7 |
Correct |
83 ms |
198696 KB |
Output is correct |
8 |
Correct |
94 ms |
198696 KB |
Output is correct |
9 |
Correct |
86 ms |
198696 KB |
Output is correct |
10 |
Correct |
90 ms |
198696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
472 ms |
199712 KB |
Output is correct - 120000 bits used |
2 |
Correct |
479 ms |
200824 KB |
Output is correct - 122000 bits used |
3 |
Correct |
482 ms |
202488 KB |
Output is correct - 125000 bits used |
4 |
Correct |
486 ms |
203384 KB |
Output is correct - 125000 bits used |
5 |
Correct |
491 ms |
204704 KB |
Output is correct - 125000 bits used |
6 |
Correct |
564 ms |
205944 KB |
Output is correct - 125000 bits used |
7 |
Correct |
507 ms |
207096 KB |
Output is correct - 124828 bits used |
8 |
Correct |
473 ms |
207992 KB |
Output is correct - 124910 bits used |
9 |
Correct |
455 ms |
209656 KB |
Output is correct - 125000 bits used |
10 |
Correct |
460 ms |
212976 KB |
Output is correct - 125000 bits used |