#include <bits/stdc++.h>
#include "advisor.h"
using namespace std;
#define s second
#define f first
void ComputeAdvice(int *C, int N, int K, int M) {
vector<int> uses(K, 0);
queue<int> nextUse[N];
for (int i = 0; i < N; i++) {
//cout << "using " << C[i] << " at " << i << endl;
nextUse[C[i]].push(i);
}
for (int i = 0; i < N; i++) {
nextUse[i].push(N);
}
// first holds next use time, second holds k-index, third holds whether its among the first k
set<pair<int, pair<int, int>>> stuff;
set<int> inSet;
map<int, int> pos;
map<int, int> revPos;
for (int i = 0; i < K; i++) {
//cout << "ADDING " << nextUse[i].front() << " " << i << " " << 1 << endl;
stuff.insert(make_pair(nextUse[i].front(), make_pair(i, 1)));
nextUse[i].pop();
inSet.insert(i);
pos[i] = i;
revPos[i] = i;
}
vector<int> count(K, 0);
for (int i = 0; i < N; i++) {
//cout << "============ ";
//for (int j = 0; j < K; j++) cout << revPos[j];
//cout << " ============" << endl;
int c = C[i];
if (inSet.count(c)) {
//cout << "used " << c << endl;
uses[pos[c]]++;
} else {
while (stuff.begin()->f < i) {
int c2 = revPos[stuff.begin()->s.f];
while (nextUse[c2].front() < i) nextUse[c2].pop();
int nextTime = nextUse[c2].front(); nextUse[c2].pop();
pair<int, int> bkup = stuff.begin()->s;
stuff.erase(stuff.begin());
stuff.insert(make_pair(nextTime, bkup));
}
pair<int, pair<int, int>> toRemove = *stuff.rbegin();
stuff.erase(--stuff.end());
if (toRemove.s.s) {
count[toRemove.s.f] = uses[toRemove.s.f];
} else {
count.push_back(uses[toRemove.s.f]);
}
uses[toRemove.s.f] = 0;
inSet.erase(toRemove.f);
int removeColor = revPos[toRemove.s.f];
//cout << "removing " << removeColor << " which is next used " << toRemove.f << endl;
//cout << "and used " << c << endl;
inSet.erase(removeColor);
pos.erase(removeColor);
revPos[toRemove.s.f] = c;
inSet.insert(c);
pos[c] = toRemove.s.f;
while (nextUse[c].front() <= i) nextUse[c].pop();
int nextTime = nextUse[c].front(); nextUse[c].pop();
stuff.insert(make_pair(nextTime, make_pair(toRemove.s.f, 0)));
}
}
for (auto x : stuff) {
if (x.s.s) count[x.s.f] = uses[x.s.f];
}
for (int i = 0; i < count.size(); i++) {
//cout << count[i] << " ";
for (int j = 0; j < count[i]; j++) WriteAdvice(1);
WriteAdvice(0);
}
//cout << endl;
}
#include <bits/stdc++.h>
#include "assistant.h"
using namespace std;
#define f first
#define s second
void Assist(unsigned char *A, int N, int K, int R) {
map<int, int> useLeft;
int idx = 0;
map<int, int> pos;
map<int, int> revPos;
queue<int> toRemove;
for (int i = 0; i < K; i++) {
int ct = 0;
while (A[idx] != 0) {
ct++;
idx++;
}
idx++;
useLeft[i] = ct;
//cout << i << " will be used " << ct << " times " << endl;
if (ct == 0) toRemove.push(i);
pos[i] = i;
revPos[i] = i;
}
for (int i = 0; i < N; i++) {
int req = GetRequest();
if (pos.count(req)) {
useLeft[pos[req]]--;
if (useLeft[pos[req]] == 0) {
toRemove.push(pos[req]);
}
} else {
int remove = toRemove.front(); toRemove.pop();
PutBack(revPos[remove]);
pos.erase(revPos[remove]);
revPos[remove] = req;
pos[req] = remove;
int ct = 0;
if (idx == R) {
ct = 10000000;
} else {
while (A[idx] != 0) {
ct++;
idx++;
}
idx++;
}
useLeft[remove] = ct;
if (ct == 0) {
toRemove.push(remove);
}
}
}
}
Compilation message
advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int i = 0; i < count.size(); i++) {
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
976 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
912 KB |
Output isn't correct - not an optimal way |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
15084 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
317 ms |
64060 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 |
12 ms |
4012 KB |
Output isn't correct - not an optimal way |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
231 ms |
146492 KB |
Execution killed with signal 11 |
| 2 |
Incorrect |
402 ms |
78768 KB |
Error - Putting back a color that is not on the scaffold |
| 3 |
Incorrect |
416 ms |
79664 KB |
Error - Putting back a color that is not on the scaffold |
| 4 |
Incorrect |
419 ms |
79436 KB |
Error - Putting back a color that is not on the scaffold |
| 5 |
Incorrect |
420 ms |
80120 KB |
Error - Putting back a color that is not on the scaffold |
| 6 |
Incorrect |
416 ms |
79940 KB |
Error - Putting back a color that is not on the scaffold |
| 7 |
Incorrect |
441 ms |
79692 KB |
Error - Putting back a color that is not on the scaffold |
| 8 |
Incorrect |
420 ms |
79836 KB |
Error - Putting back a color that is not on the scaffold |
| 9 |
Incorrect |
414 ms |
79880 KB |
Error - Putting back a color that is not on the scaffold |
| 10 |
Runtime error |
314 ms |
149032 KB |
Execution killed with signal 11 |
