| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1295349 | danirasilla | Izvanzemaljci (COI21_izvanzemaljci) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <iterator>
#include <set>
#include <random>
#include <unordered_map>
#include <queue>
#include <cassert>
#include <stack>
#include <numeric>
#include <deque>
#define int long long
using namespace std;
typedef long long ll;
typedef long double ld;
const ll md1 = 1'000'000'000;
const ll md2 = 998244353;
const ll mdd = 666013;
vector<pair<pair<int, int>, int>> cdombi(vector<pair<pair<int, int>, int>>& a, vector<pair<pair<int, int>, int>>& b) {
if (max(a[0].second, a[1].second) > max(b[0].second, b[1].second))
return b;
return a;
}
vector<pair<int, int>> a;
vector<pair<pair<int, int>, int>> getans;
bool check2(int l, int r, int k, int bou) {
vector<pair<int, int>> an(r - l);
for (int i = l; i < r; i++)
an[i - l] = a[i];
if (r - l == 1) {
getans[0] = { {an[0].first, an[0].second}, 1 };
getans[1] = { {md1 + 5, md1 + 5}, 1 };
return true;
}
for (int II = 0; II < 2; II++) {
vector<int> sx(r - l), sn(r - l);
sx[r - l - 1] = an[r - l - 1].second;
sn[r - l - 1] = an[r - l - 1].second;
for (int i = r - l - 2; i > -1; i--) {
sn[i] = min(sn[i + 1], an[i].second);
sx[i] = max(sx[i + 1], an[i].second);
}
int mn = an[0].second;
int mx = an[0].second;
for (int i = 1; i < r - l; i++) {
if (an[i - 1].first != an[i].first && an[i - 1].first - an[0].first <= k && mx - mn <= k && an[r - l - 1].first - an[i].first <= k && sx[i] - sn[i] <= k) {
getans[0] = { {an[i - 1].first - k, mn}, max(1, max(an[i - 1].first - an[0].first, mx - mn)) };
getans[1] = { {an[i].first, sn[i]}, k };
if (!II) {
if (an[i].first - 2 - bou < k)
continue;
getans[0].first.first = min(an[0].first, an[i].first - 1 - k);
}
if (II) {
swap(getans[0].first.first, getans[0].first.second);
swap(getans[1].first.first, getans[1].first.second);
}
return true;
}
mn = min(mn, an[i].second);
mx = max(mx, an[i].second);
}
for (int i = 0; i < r - l; i++)
swap(an[i].first, an[i].second);
sort(an.begin(), an.end());
}
return false;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
a.resize(n);
getans.resize(k);
for (int i = 0; i < n; i++)
cin >> a[i].first >> a[i].second;
vector<int> xa(k, md1 + 1), ya(k, md1 + 1), l(k, 1);
int ans = md1 * 2;
l[0] = ans;
xa[0] = -md1;
ya[0] = -md1;
for (int i = 1; i < k; i++)
xa[i] = md1 + i * 2, ya[i] = md1 + 2 * i;
for (int II = 0; II < 4; II++) {
sort(a.begin(), a.end());
vector<pair<pair<int, int>, int>> sufk1(n);
sufk1[n - 1] = { {a[n - 1].first, a[n - 1].second }, 1 };
{
int mx = a[n - 1].first, nx = a[n - 1].first, my = a[n - 1].second, ny = a[n - 1].second;
for (int i = n - 2; i > -1; i--) {
mx = max(mx, a[i].first);
nx = min(nx, a[i].first);
my = max(my, a[i].second);
ny = min(ny, a[i].second);
sufk1[i] = { {nx, ny}, max(mx - nx, my - ny) };
}
}
if (ans > sufk1[0].second) {
ans = sufk1[0].second;
l[0] = sufk1[0].second;
xa[0] = sufk1[0].first.first;
ya[0] = sufk1[0].first.second;
for (int i = 1; i < k; i++)
l[i] = 1, xa[i] = md1 + 2 * i, ya[i] = md1 + 2 * i;
}
if (k >= 2) {
int ll = 0;
int rr = ans;
vector<pair<pair<int, int>, int>> anss(k);
for (int i = 0; i < k; i++)
anss[i] = { {xa[i], ya[i]}, l[i] };
while (ll + 1 < rr) {
int md = (ll + rr) / 2;
bool ok = false;
if (k == 2) {
if (check2(0, n, md, -md1 * 2 - 1)) {
ok = true;
anss[0] = getans[0];
anss[1] = getans[1];
}
}
else {
int xn = a[0].first, xx = a[0].first, yn = a[0].second, yx = a[0].second;
int po = 0;
while (po < n && xx - xn <= k && yx - yn <= k) {
xn = min(xn, a[po].first);
xx = max(xx, a[po].first);
yn = min(yn, a[po].second);
yx = max(yx, a[po].second);
po++;
}
po--;
if (check2(po, n, md, a[po - 1].first)) {
ok = true;
anss[0] = getans[0];
anss[1] = getans[1];
anss[2] = { { xn, yn}, md };
}
}
if (ok)
rr = md;
else
ll = md;
}
if (rr < ans)
for (int i = 0; i < k; i++) {
ans = rr;
l[i] = anss[i].second;
xa[i] = anss[i].first.first;
ya[i] = anss[i].first.second;
}
}
for (int i = 0; i < n; i++)
a[i] = { a[i].second, -a[i].first };
for (int i = 0; i < k; i++) {
int tp = xa[i] + l[i];
xa[i] = ya[i];
ya[i] = -tp;
}
}
for (int i = 0; i < k; i++)
cout << xa[i] << " " << ya[i] << " " << l[i] << "\n";
}
return 0;
}