This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <vector>
#include <set>
#include <stack>
#include <algorithm>
#include "advisor.h"
#include <cstring>
#include <cassert>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
int out[N], lst[N], dea[N];
stack<int> nxt[N];
set<pii> s;
void ComputeAdvice(int *c, int n, int k, int m) {
memset(lst, -1, sizeof(lst));
for(int i = 0; i < n; ++i) {
nxt[i].push(N);
}
for(int i = n - 1; i >= 0; --i) {
nxt[c[i]].push(i);
if(i < k) {
s.insert({nxt[i].top(), i});
lst[i] = i;
}
}
// WriteAdvice(0);
for(int i = 0; i < n; ++i) {
auto it = s.lower_bound({nxt[c[i]].top(), c[i]});
nxt[c[i]].pop();
if(it != s.end() && it->Y == c[i]) {
out[i] = -1;
s.erase(it);
} else {
int obr = prev(s.end())->Y;
out[i] = obr;
assert(lst[obr] != -1);
dea[lst[obr]] = 1;
s.erase({nxt[obr].top(), obr});
}
s.insert({nxt[c[i]].top(), c[i]});
lst[c[i]] = i + k;
}
for(auto i : s) {
// printf("%d %d\n", i.X, i.Y);
dea[lst[i.Y]] = 1;
}
// for(int i = 0; i < n; ++i) {
// printf("%d %d %d\n", c[i], out[i], lst[i]);
// }
for(int i = 0; i < k + n; ++i) {
// printf("%d\n", dea[i]);
WriteAdvice(dea[i]);
}
}
#include <cstdio>
#include <set>
#include "assistant.h"
#include <algorithm>
#include <cassert>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
// GetRequest()
// PutBack(int x)
set<int> act[2];
void Assist(unsigned char *a, int n, int k, int r) {
for(int i = 0; i < k; ++i) {
act[a[i]].insert(i);
}
for(int i = 0; i < n; ++i) {
int x = GetRequest();
bool d = a[i + k];
auto it = act[0].lower_bound(x);
if(it != act[0].end() && *it == x) {
act[0].erase(it);
} else {
auto it2 = act[1].lower_bound(x);
// assert(it2 == act[1].end() || *it2 != x);
int out = *act[1].begin();
act[1].erase(act[1].begin());
PutBack(out);
}
act[d].insert(x);
}
}
Compilation message (stderr)
assistant.cpp: In function 'void Assist(unsigned char*, int, int, int)':
assistant.cpp:32:9: warning: variable 'it2' set but not used [-Wunused-but-set-variable]
32 | auto it2 = act[1].lower_bound(x);
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |