| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 444692 | dolphingarlic | Izvanzemaljci (COI21_izvanzemaljci) | C++14 | 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>
using namespace std;
using ll = long long;
using db = long double;
using str = string;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
template<class T> using V = vector<T>;
template<class T, size_t SZ> using AR = array<T,SZ>;
template<class T> using PR = pair<T,T>;
template<class T> int lwb(V<T>& a, const T& b)
{
return int(lower_bound(begin(a), end(a),b)-begin(a));
}
const int MOD = 1e9+7;
const int MX = 2e5+5;
const ll INF = 1e18;
const db PI = acos((db)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
constexpr int pct(int x)
{
return __builtin_popcount(x);
}
constexpr int bits(int x)
{
return x == 0 ? 0 : 31-__builtin_clz(x);
}
constexpr int p2(int x)
{
return 1<<x;
}
constexpr int msk2(int x)
{
return p2(x)-1;
}
ll cdiv(ll a, ll b)
{
return a/b+((a^b)>0&&a%b);
}
ll fdiv(ll a, ll b)
{
return a/b-((a^b)<0&&a%b);
}
template<class T> bool ckmin(T& a, const T& b)
{
return b < a ? a = b, 1 : 0;
}
template<class T> bool ckmax(T& a, const T& b)
{
return a < b ? a = b, 1 : 0;
}
template<class T, class U> T fstTrue(T lo, T hi, U first)
{
hi ++;
assert(lo <= hi);
while (lo < hi)
{
T mid = lo+(hi-lo)/2;
first(mid) ? hi = mid : lo = mid+1;
}
return lo;
}
template<class T, class U> T lstTrue(T lo, T hi, U first)
{
lo --;
assert(lo <= hi);
while (lo < hi)
{
T mid = lo+(hi-lo+1)/2;
first(mid) ? lo = mid : hi = mid-1;
}
return lo;
}
template<class T> void remDup(vector<T>& v)
{
sort(begin(v), end(v));
v.erase(unique(begin(v), end(v)),end(v));
}
template<class T, class U> void erase(T& t, const U& u)
{
auto it = t.find(u);
assert(it != end(t));
t.erase(it);
}
inline namespace Helpers
{
template<class T, class = void> struct is_iterable : false_type {};
template<class T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),
decltype(end(declval<T>()))
>
> : true_type {};
template<class T> constexpr bool is_iterable_v = is_iterable<T>::value;
template<class T, class = void> struct is_readable : false_type {};
template<class T> struct is_readable<T,
typename std::enable_if_t<
is_same_v<decltype(cin >> declval<T&>()), istream&>
>
> : true_type {};
template<class T> constexpr bool is_readable_v = is_readable<T>::value;
template<class T, class = void> struct is_printable : false_type {};
template<class T> struct is_printable<T,
typename std::enable_if_t<
is_same_v<decltype(cout << declval<T>()), ostream&>
>
> : true_type {};
template<class T> constexpr bool is_printable_v = is_printable<T>::value;
}
inline namespace Input
{
template<class T> constexpr bool needs_input_v = !is_readable_v<T> && is_iterable_v<T>;
template<class T, class ...U> void re(T& t, U&... u);
template<class T, class U> void re(pair<T,U>& p);
template<class T> typename enable_if<is_readable_v<T>,void>::type re(T& x)
{
cin >> x;
}
template<class T> void re(complex<T>& c)
{
T a,b;
re(a,b);
c = {a,b};
}
template<class T> typename enable_if<needs_input_v<T>,void>::type re(T& i);
template<class T, class U> void re(pair<T,U>& p)
{
re(p.first,p.second);
}
template<class T> typename enable_if<needs_input_v<T>,void>::type re(T& i)
{
for (auto& x: i) re(x);
}
template<class T, class ...U> void re(T& t, U&... u)
{
re(t);
re(u...);
}
void rv(size_t) {}
template<class T, class ...U> void rv(size_t N, V<T>& t, U&... u);
template<class...U> void rv(size_t, size_t N2, U&... u);
template<class T, class ...U> void rv(size_t N, V<T>& t, U&... u)
{
t.resize(N);
re(t);
rv(N,u...);
}
template<class...U> void rv(size_t, size_t N2, U&... u)
{
rv(N2,u...);
}
void decrement() {}
template<class T, class ...U> void decrement(T& t, U&... u)
{
--t;
decrement(u...);
}
}
inline namespace ToString
{
template<class T> constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>;
template<class T> typename enable_if<is_printable_v<T>,str>::type ts(T v)
{
stringstream ss;
ss << fixed << setprecision(15) << v;
return ss.str();
}
template<class T> str bit_vec(T t)
{
str res = "{";
for (int i = (0); i < (int((t).size())); ++i) res += ts(t[i]);
res += "}";
return res;
}
str ts(V<bool> v)
{
return bit_vec(v);
}
template<size_t SZ> str ts(bitset<SZ> b)
{
return bit_vec(b);
}
template<class T, class U> str ts(pair<T,U> p);
template<class T> typename enable_if<needs_output_v<T>,str>::type ts(T v);
template<class T, class U> str ts(pair<T,U> p)
{
return "("+ts(p.first)+", "+ts(p.second)+")";
}
template<class T> typename enable_if<is_iterable_v<T>,str>::type ts_sep(T v, str sep)
{
bool fst = 1;
str res = "";
for (const auto& x: v)
{
if (!fst) res += sep;
fst = 0;
res += ts(x);
}
return res;
}
template<class T> typename enable_if<needs_output_v<T>,str>::type ts(T v)
{
return "{"+ts_sep(v,", ")+"}";
}
template<int, class T> typename enable_if<!needs_output_v<T>,vs>::type
ts_lev(const T& v)
{
return {ts(v)};
}
template<int lev, class T> typename enable_if<needs_output_v<T>,vs>::type
ts_lev(const T& v)
{
if (lev == 0 || !int((v).size())) return {ts(v)};
vs res;
for (const auto& t: v)
{
if (int((res).size())) res.back() += ",";
vs tmp = ts_lev<lev-1>(t);
res.insert(end(res),begin(tmp), end(tmp));
}
for (int i = (0); i < (int((res).size())); ++i)
{
str bef = " ";
if (i == 0) bef = "{";
res[i] = bef+res[i];
}
res.back() += "}";
return res;
}
}
inline namespace Output
{
template<class T> void pr_sep(ostream& os, str, const T& t)
{
os << ts(t);
}
template<class T, class... U> void pr_sep(ostream& os, str sep, const T& t, const U&... u)
{
pr_sep(os,sep,t);
os << sep;
pr_sep(os,sep,u...);
}
template<class ...T> void pr(const T&... t)
{
pr_sep(cout,"",t...);
}
void ps()
{
cout << "\n";
}
template<class ...T> void ps(const T&... t)
{
pr_sep(cout," ",t...);
ps();
}
template<class ...T> void dbg_out(const T&... t)
{
pr_sep(cerr," | ",t...);
cerr << endl;
}
void loc_info(int line, str names)
{
cerr << "Line(" << line << ") -> [" << names << "]: ";
}
template<int lev, class T> void dbgl_out(const T& t)
{
cerr << "\n\n" << ts_sep(ts_lev<lev>(t),"\n") << "\n" << endl;
}
}
inline namespace FileIO
{
void setIn(str second)
{
freopen(second.c_str(),"r",stdin);
}
void setOut(str second)
{
freopen(second.c_str(),"w",stdout);
}
void setIO(str second = "")
{
cin.tie(0)->sync_with_stdio(0);
if (int((second).size())) setIn(second+".in"), setOut(second+".out");
}
}
int N,K;
vpl points;
pair<ll,V<pair<pl,pl>>> ans;
template<class T> void order(T& a, T& b)
{
if (a > b) swap(a,b);
}
const ll BIG = 3e9;
pair<pl,pl> make_square(ll x, ll y, ll len)
{
assert(len > 0);
assert(abs(x) <= BIG);
assert(abs(y) <= BIG);
assert(abs(x+len) <= BIG);
assert(abs(y+len) <= BIG);
return {{x,y},{x+len,y+len}};
}
void fail(bool b, bool flag)
{
if (b)
{
exit(flag);
}
}
pair<ll,V<pair<pl,pl>>> eval(V<pair<pl,pl>> cand)
{
ll len = 0;
for (auto& t: cand) ckmax(len,abs(t.second.first-t.first.first));
return {len,cand};
}
void check(V<pair<pl,pl>> cand, bool flag = false)
{
assert(int((cand).size()) <= K);
for (auto& t: cand)
{
fail(abs(t.first.first) > BIG,flag);
fail(abs(t.first.second) > BIG,flag);
fail(abs(t.second.first) > BIG,flag);
fail(abs(t.second.second) > BIG,flag);
}
int cnt = 0;
while (int((cand).size()) < K)
{
if (cnt == 0)
{
cand.push_back(make_square(BIG-5,BIG-5,1));
}
else
{
cand.push_back(make_square(-BIG+5,-BIG+5,1));
}
++cnt;
}
for (auto& t: cand)
{
fail(abs(t.first.first) > BIG,flag);
fail(abs(t.first.second) > BIG,flag);
fail(abs(t.second.first) > BIG,flag);
fail(abs(t.second.second) > BIG,flag);
}
ckmin(ans,eval(cand));
}
using Square = pair<pl,pl>;
vpl rev(vpl v)
{
reverse(begin(v), end(v));
return v;
}
vpl neg(vpl v)
{
for (auto& t: v) t.first *= -1;
return v;
}
V<Square> get_prefs(vpl v)
{
ll xl = v[0].first, xr = v[0].first;
ll yl = v[0].second, yr = v[0].second;
V<Square> prefs;
for (int i = (0); i < (int((v).size())); ++i)
{
ckmin(xl,v[i].first), ckmax(xr,v[i].first);
ckmin(yl,v[i].second), ckmax(yr,v[i].second);
ll len = max({xr-xl,yr-yl,1LL});
prefs.push_back(make_square(xr-len,yl,len));
}
return prefs;
}
V<Square> neg(V<Square> v)
{
for (auto& t: v) t.first.first *= -1, t.second.first *= -1;
return v;
}
ll get_len(Square sq)
{
ll dif = sq.second.first-sq.first.first;
assert(dif > 0);
return dif;
}
pair<ll,V<Square>> solve_opt_2(vpl rem)
{
assert(int((rem).size()));
V<Square> pref_square = get_prefs(rem);
V<Square> suf_square = neg(get_prefs(rev(neg(rem))));
reverse(begin(suf_square), end(suf_square));
pair<ll,V<Square>> res = eval({pref_square.back()});
for (int i = (0); i < (int((rem).size())-1); ++i) if (rem.at(i).first < rem.at(i+1).first)
ckmin(res,eval({pref_square.at(i),suf_square.at(i+1)}));
return res;
}
V<Square> swap_xy_sq(V<Square> v)
{
for (auto& t: v)
{
swap(t.first.first,t.first.second);
swap(t.second.first,t.second.second);
}
return v;
}
void solve()
{
sort(begin(points), end(points));
V<Square> pref_square = get_prefs(points);
V<Square> suf_square = neg(get_prefs(rev(neg(points))));
reverse(begin(suf_square), end(suf_square));
{
check({pref_square.back()});
}
if (K >= 2)
{
for (int i = (0); i < (int((pref_square).size())-1); ++i) if (points[i].first < points[i+1].first)
{
check({pref_square[i],suf_square[i+1]}, true);
}
}
if (K >= 3)
{
vi tri_inds;
for (int i = (0); i < (int((points).size())-1); ++i) if (points.at(i).first < points.at(i+1).first)
{
tri_inds.push_back(i);
}
vl huh;
auto check_sol = [&](int ind) -> ll
{
auto swap_xy = [&](pl p)
{
swap(p.first,p.second);
return p;
};
vpl rem;
for (int i = (ind+1); i < (int((points).size())); ++i) rem.push_back(swap_xy(points.at(i)));
sort(begin(rem), end(rem));
auto ans_y = solve_opt_2(rem);
ans_y.second = swap_xy_sq(ans_y.second);
for (auto& t: ans_y.second) assert(t.first.first > points.at(ind).first && t.second.first > points.at(ind).first);
ll xl = MOD, xr = -MOD;
ll yl = MOD, yr = -MOD;
for (int i = (ind+1); i < (int((points).size())-1); ++i)
{
ckmin(xl,points.at(i).first);
ckmax(xr,points.at(i).first);
ckmin(yl,points.at(i).second);
ckmax(yr,points.at(i).second);
if (points.at(i).first < points.at(i+1).first)
{
ll len = max({xr-xl,yr-yl,1LL});
ll nxl = max(points.at(ind).first+1,xr-len);
ll nxr = nxl+len;
if (nxr < points.at(i+1).first)
{
ckmin(ans_y,eval({make_square(nxl,yl,len),suf_square.at(i+1)}));
}
}
}
huh.push_back(ans_y.first);
ans_y.second.push_back(pref_square.at(ind));
ans_y = eval(ans_y.second);
ckmin(ans,ans_y);
return ans_y.first;
};
int lo = 0, hi = int((tri_inds).size())-1;
while (lo <= hi)
{
int mid = (lo+hi)/2;
int x = tri_inds.at(mid);
ll len = check_sol(x);
if (len > get_len(pref_square.at(x))) lo = mid+1;
else hi = mid-1;
}
}
}
template<class T> void rot(T& p)
{
p = make_pair(-p.second,p.first);
}
int main()
{
setIO();
re(N,K);
points.resize(N);
re(points);
ans.first = 2*MOD;
for (int _ = (0); _ < (4); ++_)
{
solve();
for (auto& t: points) rot(t);
for (auto& t: ans.second) rot(t.first), rot(t.second);
}
ll len = 0;
for (auto& t: ans.second)
{
pl a = t.first;
pl b = t.second;
order(a.first,b.first);
order(a.second,b.second);
assert(b.first-a.first == b.second-a.second);
ckmax(len,b.first-a.first);
assert(abs(a.first) <= BIG);
assert(abs(a.second) <= BIG);
ps(a.first,a.second,b.first-a.first);
}
0;
}