# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1071048 | sleepntsheep | Ancient Machine (JOI21_ancient_machine) | C++17 | 102 ms | 17920 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 "Anna.h"
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
namespace {
}
void Anna(int N, std::vector<char> S) {
int freq[3] {}, ord[3] {};
for (char c : S) ++freq[(int)(c - 'X')];
int o[3] = {0, 1, 2};
sort(o, o + 3, [&](int a, int b){ return freq[a] > freq[b]; });
int j = 0;
for (auto x : o) {
Send(x >> 1);
Send(x & 1);
ord[x] = j++;
}
for (int i = 0; i < N; ++i) {
int v = S[i] - 'X';
switch (ord[v]) {
case 0:
Send(0);
break;
case 1:
Send(1);
Send(0);
break;
case 2:
Send(1);
Send(1);
break;
}
}
}
#include "Bruno.h"
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
namespace {
vector<int> decode(int N, vector<int> A) {
int m1, m2, m3;
vector<int> v;
m1 = A[0] * 2 + A[1], m2 = A[2] * 2 + A[3], m3 = A[4] * 2 + A[5];
for (int i = 6; i < (int)A.size(); )
if (A[i] == 0)
v.push_back(m1), ++i;
else
v.push_back((A[i + 1]) ? m3 : m2), ++i, ++i;
return v;
}
} // namespace
void Bruno(int N, int L, vector<int> A) {
auto v = decode(N, A);
set<int> alv;
vector<int> ded(N);
for (int i = 0; i < N; ++i) alv.insert(i);
vector<set<int> > oc(3);
for (int i = 0; i < N; ++i)
oc[v[i]].insert(i);
if (oc[0].empty() or oc[2].empty() or *oc[0].begin() > *oc[2].rbegin()) {
for (int i = 0; i < N; ++i) Remove(i);
return;
}
int x0 = *oc[0].begin();
int z0 = *oc[2].rbegin();
auto REmove = [&](int i) { if (alv.count(i) == 0) return; alv.erase(i); oc[v[i]].erase(i); Remove(i); };
auto REmove_range = [&](int i, int j) {
for (auto it = alv.lower_bound(i); it != alv.end() && *it <= j; )
Remove(*it), oc[v[*it]].erase(*it), it = alv.erase(it);
};
int at = x0;
for (; at < z0 ;) {
auto zi = oc[2].upper_bound(at);
while (1) {
auto yi = oc[1].lower_bound(*zi);
if (yi == oc[1].begin() or *--yi < x0)
break;
auto xi = prev(oc[0].lower_bound(*yi));
REmove_range(*xi + 1, *yi - 1);
REmove_range(*yi + 1, *zi - 1);
REmove(*yi);
if (*xi != x0) REmove(*xi);
}
REmove_range(at + 1, *zi - 1);
at = *zi;
}
for (int i = 0; i < N; ++i) REmove(i);
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |