| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 881470 | eitanelb | Cultivation (JOI17_cultivation) | 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<vector>
#include<iostream>
#include<set>
#include<algorithm>
#include "frogs.h"
using namespace std;
#define pi pair<int,int>
#define x first
#define y second
/*
for down - just real distances from down (optional also for left) -> O(n)
for up - just real distances, or such that together it's distance between two -> O(n)+O(n^2)
after I have up and down - O(n^2) //optional - O(nlogu), with segmentree sparse/coordination, then O(n^4 logU)
then O(n^5), or if r<=40 -> O(40*40*40*n)
which is 60 points
for 100 points, let's see that whenever you get the up bigger, it affects only one place
that can being it to O(n^3), which is 100 points
*/
int deb = 0;
pair<int, pi>* merge(pair<int, pi>* v1, pair<int, pi>* v2, int n1, int n2) {
pair<int, pi>* v3 = new pair<int, pi>[n1 + n2];
int p1 = 0, p2 = 0, p3 = 0;
while (p1 < n1 || p2 < n2) {
if (p1 != n1 && (p2 == n2 || v1[p1].x <= v2[p2].x)) v3[p3++] = v1[p1++];
else v3[p3++] = v2[p2++];
}
return v3;
}
int Time_To_Fool_The_Lab(int r, int c, int n, vector<int> X, vector<int> Y) {
int* vdown = new int[n];
pair<int, pi>* vup = new pair<int, pi>[n];
//int sz = n * (n - 1) / 2;
int sz = 0;
for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)if (X[i] > X[j])++sz;
pair<int, pi>* vsum = new pair<int, pi>[sz];
int t = 0;
for (int i = 0; i < n; ++i) {
vdown[i] = X[i] - 1;
}
for (int i = 0; i < n; ++i) {
vup[i] = { r - X[i], {i, -1} };
for (int j = 0; j < n; ++j) if (X[i] > X[j]) vsum[t++] = { X[i] - X[j] - 1, {i, j} };
}
sort(vdown, vdown + n);
int h = unique(vdown, vdown + n) - vdown;
sort(vup, vup + n);
sort(vsum, vsum + sz);
int res = 2e9;
for (int d = 0; d < h; d++) {
int down = vdown[d];
pair<int, pi>* vnup = new pair<int, pi>[sz];
for (int i = 0; i < sz; i++) vnup[i] = { vsum[i].x - down,vsum[i].y };
vnup = merge(vnup, vup, sz, n);
bool* on = new bool[n];
int* dr = new int[n], * dl = new int[n], * maxi = new int[n], * disl = new int[n], * disr = new int[n];
for (int i = 0; i < n; i++) {
on[i] = 0;
if (X[i] == r) {
dr[i] = dl[i] = 0;
on[i] = 1;
disl[i] = disr[i] = 0;
continue;
}
dr[i] = c - Y[i];
dl[i] = Y[i] - 1;
disl[i] = disr[i] = c;
for (int j = 0; j < n; j++) {
if (j == i) continue;
if (X[j] > X[i] && X[j] - down <= X[i] + 1) {
if (Y[j] > Y[i]) dr[i] = min(dr[i], Y[j] - Y[i] - 1);
else if (Y[j] < Y[i]) dl[i] = min(dl[i], Y[i] - Y[j] - 1);
else on[i] = 1;
disr[i] = min(disr[i], c - Y[j]);
disl[i] = min(disl[i], Y[j] - 1);
}
}
}
if (deb) { cout << "disl: "; for (int i = 0; i < n; i++) cout << disl[i] << ' '; cout << endl; }
if (deb) { cout << "disr: "; for (int i = 0; i < n; i++) cout << disr[i] << ' '; cout << endl; }
multiset<int> maxs, sdl, sdr;
for (int i = 0; i < n; i++) {
if (on[i]) maxi[i] = max(dr[i], dl[i]);
else maxi[i] = dr[i] + dl[i] + 1;
maxs.insert(maxi[i]);
sdl.insert(disl[i]);
sdr.insert(disr[i]);
}
if (deb) { for (int i = 0; i < n; i++) { cout << dl[i] << ' ' << dr[i] << ' ' << maxi[i] << ' ' << on[i] << endl; } }
// row 1 ************
int mx1 = 0;
set<int> st;
for (int i = 0; i < n; i++)
if (X[i] - down <= 1)
st.insert(Y[i]);
sdl.insert(*st.begin() - 1);
sdr.insert(c - *prev(st.end()));
int fr = 0;
for (int i : st) {
mx1 = max(mx1, i - fr - 1);
fr = i;
}
maxs.insert(mx1);
int up = 0;
for (int q = 0; q < (n + sz); q++) {
if (deb) { cout << "disl: "; for (int i = 0; i < n; i++) cout << disl[i] << ' '; cout << endl; }
if (deb) { cout << "disr: "; for (int i = 0; i < n; i++) cout << disr[i] << ' '; cout << endl; }
pair<int, pi> pr = vnup[q];
if (deb) { cout << pr.x << ' ' << pr.y.x << ' ' << pr.y.y << endl; }
up = pr.x;
if (down + up >= res) continue;
if (up < 0) continue;
if (pr.y.y == -1) {
int u = pr.y.x;
maxs.erase(maxs.find(maxi[u]));
sdl.erase(sdl.find(disl[u]));
sdr.erase(sdr.find(disr[u]));
}
else {
int i = pr.y.x, j = pr.y.y;
if (Y[i] == Y[j]) on[j] = 1;
else if (Y[i] > Y[j]) {
if (dr[j] > Y[i] - Y[j] - 1) {
dr[j] = Y[i] - Y[j] - 1;
}
}
else {
if (dl[j] > Y[j] - Y[i] - 1) {
dl[j] = Y[j] - Y[i] - 1;
}
}
sdl.erase(sdl.find(disl[j]));
sdr.erase(sdr.find(disr[j]));
disr[j] = min(disr[j], c - Y[i]);
disl[j] = min(disl[j], Y[i] - 1);
sdl.insert(disl[j]);
sdr.insert(disr[j]);
maxs.erase(maxs.find(maxi[j]));
if (on[j]) maxi[j] = max(dr[j], dl[j]);
else maxi[j] = dr[j] + dl[j] + 1;
maxs.insert(maxi[j]);
}
int mxla = *prev(sdl.end()), mxfa = *prev(sdr.end());
int mx = *prev(maxs.end());
if (mxla >= c || mxfa >= c) continue;
mx = max(mx, mxla + mxfa);
if (mx > 2e9 - up - down) continue;
if (deb) {
cout << mx << ' ' << mxla << ' ' << mxfa << ' ' << up << ' ' << down << endl;
}
res = min(res, mx + down + up);
}
}
return res;
}
#include<iostream>
#include<vector>
#include<string>
#include<fstream>
using namespace std;
int run = 1;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
if (run == 1) {
int R, C, N;
cin >> R >> C >> N;
vector<int> X(N), Y(N);
for (int i = 0; i < N; i++) {
cin >> X[i] >> Y[i];
}
int res = Time_To_Fool_The_Lab(R, C, N, X, Y);
cout << res << endl;
}
if (run == 2) {
vector<int> sizes = { 0, 16, 16, 12, 20, 16, 18 };
string name = "01-01";
for (int j = 6; j < 7; j++) {
cout << "****" << j << "****\n";
name[1] = '0' + j;
for (int i = 1; i <= sizes[j]; i++) {
cout << "**" << j << ' ' << i << "**\n";
name[3] = '0' + i / 10; name[4] = '0' + i % 10;
ifstream fin(name + ".in"), fout(name + ".out");
int R, C, N;
fin >> R >> C >> N;
vector<int> X(N), Y(N);
for (int i = 0; i < N; i++) {
fin >> X[i] >> Y[i];
}
int nres, res = Time_To_Fool_The_Lab(R, C, N, X, Y);
fout >> nres;
if (nres != res) {
cout << "subtask " << j << "test" << i << endl;
cout << R << ' ' << C << endl << N << endl;
for (int i = 0; i < N; i++) {
cout << X[i] << ' ' << Y[i] << endl;
}
cout << res << ' ' << nres << endl;
break;
}
}
}
}
}