| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 417322 | maomao90 | Ancient Machine (JOI21_ancient_machine) | 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 "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb emplace_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 200005
namespace {
int n, l;
vi a;
vector<char> s;
vi lft;
set<int> ys, zs, xs;
vector<iii> ans;
bool isPos(int x) {
int ptr = 0;
lft.clear();
ys.clear(); zs.clear(); xs.clear();
ans.clear();
REP (i, 0, n) {
if (s[i] == 'Y') ys.insert(i);
else if (s[i] == 'Z') zs.insert(i);
else if (s[i] == 'X') xs.insert(i);
}
REP (i, 0, x) {
while (ptr < n && s[ptr] != 'X') ptr++;
if (ptr >= n) return 0;
lft.pb(ptr++);
}
REP (i, 0, x) {
int u = lft.back();
auto tmp = ys.lower_bound(u);
if (tmp == ys.end()) return 0;
int ny = *tmp;
auto tmpp = zs.lower_bound(ny);
if (tmpp == zs.end()) return 0;
int nz = *tmpp;
int py = *prev(ys.lower_bound(nz));
int px = *prev(xs.lower_bound(py));
auto ptr = xs.lower_bound(px);
while (ptr != xs.end() && *ptr <= nz) {
auto nxt = next(ptr);
xs.erase(ptr);
ptr = nxt;
}
ptr = ys.lower_bound(px);
while (ptr != ys.end() && *ptr <= nz) {
auto nxt = next(ptr);
ys.erase(ptr);
ptr = nxt;
}
ptr = zs.lower_bound(px);
while (ptr != zs.end() && *ptr <= nz) {
auto nxt = next(ptr);
zs.erase(ptr);
ptr = nxt;
}
if (px == u) {
lft.pop_back();
}
ans.pb(px, py, nz);
}
return 1;
}
bool solve(int x) {
int ptr = 0;
lft.clear();
ys.clear(); zs.clear(); xs.clear();
ans.clear();
REP (i, 0, n) {
if (s[i] == 'Y') ys.insert(i);
else if (s[i] == 'Z') zs.insert(i);
else if (s[i] == 'X') xs.insert(i);
}
REP (i, 0, x) {
while (ptr < n && s[ptr] != 'X') ptr++;
if (ptr >= n) return 0;
lft.pb(ptr++);
}
REP (i, 0, x) {
int u = lft.back();
auto tmp = ys.lower_bound(u);
if (tmp == ys.end()) return 0;
int ny = *tmp;
auto tmpp = zs.lower_bound(ny);
if (tmpp == zs.end()) return 0;
int nz = *tmpp;
int py = *prev(ys.lower_bound(nz));
int px = *prev(xs.lower_bound(py));
auto ptr = xs.lower_bound(px);
while (ptr != xs.end() && *ptr <= nz) {
auto nxt = next(ptr);
if (*ptr != px) {
Remove(*ptr);
}
xs.erase(ptr);
ptr = nxt;
}
ptr = ys.lower_bound(px);
while (ptr != ys.end() && *ptr <= nz) {
auto nxt = next(ptr);
if (*ptr != py) {
Remove(*ptr);
}
ys.erase(ptr);
ptr = nxt;
}
ptr = zs.lower_bound(px);
while (ptr != zs.end() && *ptr <= nz) {
auto nxt = next(ptr);
if (*ptr != nz) {
Remove(*ptr);
}
zs.erase(ptr);
ptr = nxt;
}
if (px == u) {
lft.pop_back();
}
Remove(py);
ans.pb(px, py, nz);
}
for (auto i : xs) {
Remove(i);
}
for (auto i : ys) {
Remove(i);
}
for (auto i : zs) {
Remove(i);
}
return 1;
}
}
void Bruno(int N, int L, vi A) {
n = N; l = L; a = A;
REP (i, 0, n) {
int x = a[i * 2], y = a[i * 2 + 1];
if (x == 0) {
if (y == 0) {
s.pb('X');
} else {
s.pb('Y');
}
} else {
s.pb('Z');
}
}
int lo = 0, hi = n, mid;
int res = -1;
while (lo <= hi) {
int mid = lo + hi >> 1;
if (isPos(mid)) {
res = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
assert(res != -1);
solve(res);
}