Submission #419326

#	Time	Username	Problem	Language	Result	Execution time	Memory
419326		2qbingxuan	Cultivation (JOI17_cultivation)	C++14	0 / 100	2060 ms	204 KiB

cultivation

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#ifdef local
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define pary(a...) danb(#a, a)
#define debug(a...) qqbx(#a, a)
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\033[1;32m(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : ")\033[0m\n")));
}
template <typename T> void danb(const char *s, T L, T R) {
    std::cerr << "\033[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        std::cerr << (f++ ? ", " : "") << *L;
    std::cerr << " ]\033[0m\n";
}
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#define pary(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)
#define pb emplace_back
#define get_pos(u,x) int(lower_bound(all(u),x)-begin(u))

using namespace std;
using ll = int_fast64_t;
using ld = long double;
template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
const int mod = 1000000007;
const int inf = 1e9;
const ll INF = 1e18;
const int maxn = 101;
template <typename T> void sort_uni(T &v) { sort(all(v)), v.erase(unique(all(v)), v.end()); }

int solve(int R, int C, vector<pair<int,int>> pts) {
    int N = pts.size();
    auto proc = [&]() {
        sort(all(pts));

        vector<int> dx{0};
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i; j++) {
                dx.emplace_back(pts[i].first - pts[j].first - 1);
            }
            dx.emplace_back(pts[i].first - 1);
            dx.emplace_back(R - pts[i].first);
        }
        sort_uni(dx);

        int mina = pts[0].first - 1;
        int minb = R - pts[N-1].first;
        int minsum = 0;
        for (int i = 1; i < N; i++) minsum = max(minsum, pts[i].first - pts[i-1].first - 1);
        debug(mina, minb, minsum);
        pary(all(dx));

        vector<int> Y(N);
        for (int i = 0; i < N; i++)
            Y[i] = pts[i].second;
        for (int i = 0; i < N; i++) {
            int rk = 0;
            for (int j = 0; j < N; j++)
                if (i != j && pts[i].second > Y[j])
                    ++rk;
            pts[i].second = rk + 1;
        }

        vector<vector<int>> Ydiff(N + 1, vector<int>(N + 1));
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                Ydiff[i+1][j+1] = abs(Y[i] - Y[j]);

        auto calc = [&](int a, int b) {
            vector<pair<int,int>> evt;
            evt.reserve(N*2);
            for (auto [x, y]: pts) evt.emplace_back(x-a, y);
            for (auto [x, y]: pts) evt.emplace_back(x+b+1, -y);
            inplace_merge(evt.begin(), evt.begin() + N, evt.end());

            bitset<maxn> bs;
            vector<int> cnt(N+1);

            auto add = [&](int val) {
                if (cnt[val]++ == 0)
                    bs[val] = true;
                // posy.insert(lower_bound(all(posy), val), val);
            };
            auto remove = [&](int val) {
                if (--cnt[val] == 0)
                    bs[val] = false;
                // posy.erase(find(all(posy), val));
            };
            int ans = 0, minc = 0, mind = 0;
            for (int i = 0, j = 0; i < N*2; i = j) {
                for (j = i; j < N*2; j++) {
                    if (evt[j].first != evt[i].first) break;
                    int y = evt[j].second;
                    if (y < 0) {
                        remove(-y);
                    } else {
                        add(y);
                    }
                }
                if (j == N*2) continue;
                int l = evt[i].first;
                int r = evt[j].first;
                if (r <= 1 || l > R) continue;
                // assert (posy.size() > 0);
                // minc = max(minc, posy.front() - 1);
                // mind = max(mind, C - posy.back());
                /*
                if (posy.size() >= 2) {
                    for (int k = 1; k < posy.size(); k++) {
                        ans = max(ans, posy[k] - posy[k-1] - 1);
                    }
                }
                */
                minc = max(minc, Y[bs._Find_first()] - 1);
                int last = -1;
                for (int i = bs._Find_first(); i != maxn; i = bs._Find_next(i)) {
                    if (last != -1) {
                        ans = max(ans, i - last);
                    }
                    last = i;
                }
                mind = max(mind, C - Y[last]);
            }
            ans = max(ans, minc + mind);
            return ans;
            debug(a, b, ans);
            debug(minc, mind);
        };
        int res = 2e9;
        for (int a: dx) {
            if (a < mina) continue;
            for (int b: dx) {
                if (b < minb) continue;
                if (a + b < minsum) continue;
                res = min<ll>(res, 0LL + a + b + calc(a, b));
            }
        }

        for (int a: dx) {
            if (a < mina) continue;
            for (int d: dx) {
                if (d < a) continue;
                int b = d - a;
                if (b < minb || a + b < minsum) continue;
                res = min<ll>(res, 0LL + a + b + calc(a, b));
            }
        }

        return res;
    };
    // int res = proc();
    // for (auto &[x, y]: pts) swap(x, y);
    // swap(R, C);
    // return min(res, proc());
    return proc();
}

int naive(int R, int C, vector<pair<int,int>> pts) {
    int grid = 0;
    for (auto [x, y]: pts) grid |= 1<<((x-1) * C + (y-1));
    unordered_map<int,int> dis;
    const int U = (1 << (R*C)) - 1;
    queue<int> q;
    dis[grid] = 0;
    q.push(grid);

    int mask1 = 0, mask2 = 0;
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) {
        if (j - 1 >= 0)
            mask1 |= 1 << (i * C + j);
        if (j + 1 < C)
            mask2 |= 1 << (i * C + j);
    }
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        if (int nxt = (cur | cur << C) & U; !dis.count(nxt))
            dis[nxt] = dis[cur] + 1, q.push(nxt);

        if (int nxt = (cur | cur >> C); !dis.count(nxt))
            dis[nxt] = dis[cur] + 1, q.push(nxt);

        if (int nxt = cur | ((cur & mask1) >> 1); !dis.count(nxt))
            dis[nxt] = dis[cur] + 1, q.push(nxt);

        if (int nxt = cur | ((cur & mask2) << 1); !dis.count(nxt))
            dis[nxt] = dis[cur] + 1, q.push(nxt);
    }
    return dis[U];
}
void verify() {
    int R, C;
    cin >> R >> C;
    for (int i = 1; i < (1<<(R*C)); i++) {
        vector<pair<int,int>> pts;
        for (int j = 0; j < R*C; j++) if (i >> j & 1) pts.emplace_back(j / C + 1, j % C + 1);
        int na = naive(R, C, pts);
        int ca = solve(R, C, pts);
        if (na != ca) {
            debug(na, ca);
            for (auto [x, y]: pts) cerr<<x<<','<<y<<'\n';
            exit(3);
        }
    }
    exit(0);
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    // verify();

    int R, C, N;
    cin >> R >> C >> N;
    vector<pair<int,int>> pts(N);
    for (auto &[x, y]: pts) cin >> x >> y;
    cerr << naive(R, C, pts) << '\n';
    cout << solve(R, C, pts) << '\n';
}

/*
   4 4 2
   1 2
   2 1

   4 3 2
   1 1
   1 3

   10 1 2
   2 1
   8 1
   */

Compilation message (stderr)

cultivation.cpp: In lambda function:
cultivation.cpp:77:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |             for (auto [x, y]: pts) evt.emplace_back(x-a, y);
      |                       ^
cultivation.cpp:78:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |             for (auto [x, y]: pts) evt.emplace_back(x+b+1, -y);
      |                       ^
cultivation.cpp: In function 'int naive(int, int, std::vector<std::pair<int, int> >)':
cultivation.cpp:165:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  165 |     for (auto [x, y]: pts) grid |= 1<<((x-1) * C + (y-1));
      |               ^
cultivation.cpp:181:13: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17'
  181 |         if (int nxt = (cur | cur << C) & U; !dis.count(nxt))
      |             ^~~
cultivation.cpp:184:13: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17'
  184 |         if (int nxt = (cur | cur >> C); !dis.count(nxt))
      |             ^~~
cultivation.cpp:187:13: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17'
  187 |         if (int nxt = cur | ((cur & mask1) >> 1); !dis.count(nxt))
      |             ^~~
cultivation.cpp:190:13: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17'
  190 |         if (int nxt = cur | ((cur & mask2) << 1); !dis.count(nxt))
      |             ^~~
cultivation.cpp: In function 'void verify()':
cultivation.cpp:205:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  205 |             for (auto [x, y]: pts) cerr<<x<<','<<y<<'\n';
      |                       ^
cultivation.cpp: In function 'int main()':
cultivation.cpp:218:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  218 |     for (auto &[x, y]: pts) cin >> x >> y;
      |                ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20