#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);
}
Compilation message
Anna.cpp: In function 'void Bruno(int, int, vi)':
Anna.cpp:178:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
178 | int mid = lo + hi >> 1;
| ~~~^~~~
Anna.cpp:175:22: warning: unused variable 'mid' [-Wunused-variable]
175 | int lo = 0, hi = n, mid;
| ^~~
/usr/bin/ld: /tmp/ccp9JFQ1.o: in function `main':
grader_anna.cpp:(.text.startup+0x14c): undefined reference to `Anna(int, std::vector<char, std::allocator<char> >)'
/usr/bin/ld: /tmp/ccXCpD61.o: in function `Bruno(int, int, std::vector<int, std::allocator<int> >)':
Anna.cpp:(.text+0x1175): undefined reference to `Remove(int)'
/usr/bin/ld: Anna.cpp:(.text+0x121e): undefined reference to `Remove(int)'
/usr/bin/ld: Anna.cpp:(.text+0x12ca): undefined reference to `Remove(int)'
/usr/bin/ld: Anna.cpp:(.text+0x1320): undefined reference to `Remove(int)'
/usr/bin/ld: Anna.cpp:(.text+0x145d): undefined reference to `Remove(int)'
/usr/bin/ld: /tmp/ccXCpD61.o:Anna.cpp:(.text+0x1481): more undefined references to `Remove(int)' follow
collect2: error: ld returned 1 exit status
/usr/bin/ld: /tmp/ccbqThAN.o: in function `main':
grader_bruno.cpp:(.text.startup+0x24d): undefined reference to `Bruno(int, int, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
