# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
988441 | vjudge1 | Last supper (IOI12_supper) | C++17 | 0 ms | 0 KiB |
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 <bits/stdc++.h>
#include "advisor.h"
#include "assistant.h"
#define ll long long
#define endl '\n'
#define pii pair<int,int>
#define vint vector<int>
#define vpii vector<pii>
#define se second
#define fi first
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
const int N = (int)2e5 + 69;
const int mod = 1000000007;
const int base = 313;
const int INF = INT_MAX;
int power(int a, int bb) { int ans = 1;while (bb) { if (bb % 2) { ans *= a; }a *= a;bb /= 2; }return ans; }
int gcd(int a, int b) { if (b == 0)return a;return gcd(b, a % b); }
void ComputeAdvice(int c[], int n, int k, int m) {
vint mp(n,0);
vint pos[N];
set<pii> s;
vint advice(n+k, 0);
for (int i = 0; i < n; i++)
pos[c[i]].pb(i);
for (int i = 0; i < k; i++) {
mp[i] = 1;
if (!pos[i].size())
s.insert({ -INF,i});
else
s.insert({ -pos[i][0],i });
}
for (int i = 0; i < n; i++) {
if(!mp[c[i]]) {
pii tmp = *s.begin();
s.erase(s.begin());
advice[tmp.se] = 1;
mp[c[i]] = 1;
if (tmp.se < k)
mp[tmp.se] = 0;
else
mp[c[tmp.se - k]] = 0;
}
int idx = upper_bound(all(pos[c[i]]), i) - pos[c[i]].begin();
if (idx == pos[c[i]].size())
s.insert({ -INF,i + k });
else
s.insert({ -pos[c[i]][idx],i + k });
}
for (int i = 0; i < n + k; i++)
WriteAdvice(advice[i]);
}
void Assist(unsigned char* a, int n, int k, int R) {
vint st;
vint mp(n,0);
for (int i = 0; i < k; i++) {
mp[i] = 1;
if (a[i])
st.pb(i);
}
for (int i = 0; i < n; i++) {
int c = GetRequest();
if (!mp[c]) {
PutBack(st.back());
mp[st.back()] = 0;
mp[c] = 1;
st.pop_back();
}
if (a[i + k])
st.pb(c);
}
return;
}
//int32_t main() {
//
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//
//
//}