Submission #873313

#	Time	Username	Problem	Language	Result	Execution time	Memory
873313		bobbilyking	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	16 ms	72280 KiB

joioi

// thsi submission is hilariously wrong

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include<bits/stdc++.h>
#include<math.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = (l); i < r; ++i)

#define NN 2010
#define M 1000000007 // 998244353

ll numValid; // init to rows+columns

struct counter {
    ll mex = 0, sz = 0;
    bitset<NN> see;
    void update(ll idx) {
        assert(!see[idx]);
        numValid -= mex == sz;
        sz++;
        see[idx] = 1;
        while (see[mex]) ++mex;
        numValid += mex == sz;
    }
} rows[NN], cols[NN];

ll ccs = 0;
ll to(ll i, ll j){
    return i * NN + j;
}

//DSU
ll parent[NN*NN], sz[NN*NN];
ll find(ll a){ return a == parent[a] ? a : parent[a] = find(parent[a]); }
void merge(ll u, ll v) {
    u = find(u), v=find(v);
    if (u!=v) {
        if (sz[u]<sz[v]) swap(u, v);
        sz[u] += sz[v];
        parent[v] = u;
        ccs--;
    }
}

bool filled[NN][NN];
bool vfront[NN*NN], vback[NN*NN];

int main(){
//    freopen("a.in", "r", stdin);
//    freopen("a.out", "w", stdout);

    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(20);
    G(n) G(m)
    vector<pair<ll, pl>> a;
    F(i, 0, n) {
        F(j, 0, m) {
            G(x) a.emplace_back(x, pl{i, j});
        }
    }
    ll dx[4] = {-1, 0, 1, 0};
    ll dy[4] = {0, -1, 0, 1};

    sort(A(a));
    ll ans = a.back().K - a.begin()->K;
    {
        ccs = 0;
        F(i, 0, NN) F(j, 0, NN) {
            filled[i][j] = sz[to(i, j)] = 1;
            parent[to(i, j)] = to(i, j); 
        }

        F(idx, 0, a.size()) {
            auto [i, j] = a[idx].V;
            filled[i][j] = 1; ccs++;
            F(k, 0, 4) {
                ll ni = i + dx[k], nj = j + dy[k];
                if (min(ni, nj) >= 0 and ni < n and nj < m and filled[ni][nj]) {
                    merge(to(ni, nj), to(i, j));
                }
            }
            vfront[idx] = ccs==1; 
        }
    }
    {
        ccs = 0;
        F(i, 0, NN) F(j, 0, NN) {
            filled[i][j] = sz[to(i, j)] = 1;
            parent[to(i, j)] = to(i, j); 
        }

        for (ll idx = ll(a.size())-1; idx >= 0; --idx) {
            auto [i, j] = a[idx].V;
            filled[i][j] = 1; ccs++;
            F(k, 0, 4) {
                ll ni = i + dx[k], nj = j + dy[k];
                if (min(ni, nj) >= 0 and ni < n and nj < m and filled[ni][nj]) {
                    merge(to(ni, nj), to(i, j));
                }
            }
            vback[idx] = ccs==1; 
        }
    }

    F(k, 0, n)
    numValid = n+m;
    F(idx, 0, a.size()) {
        auto [i, j] = a[idx].V;
        rows[i].update(j); cols[j].update(i);
        if (numValid == n+m and vfront[idx] and vback[idx+1]) {
            ans = min(ans, 
                max(a[idx].K - a.begin()->K, a.back().K - a[idx+1].K)
            );
        }
    }

    cout << ans << '\n';
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:84:41: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   84 |             filled[i][j] = sz[to(i, j)] = 1;
      |                            ~~~~~~~~~~~~~^~~
joioi.cpp:22:39: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define F(i, l, r) for (ll i = (l); i < r; ++i)
......
   88 |         F(idx, 0, a.size()) {
      |           ~~~~~~~~~~~~~~~~             
joioi.cpp:88:9: note: in expansion of macro 'F'
   88 |         F(idx, 0, a.size()) {
      |         ^
joioi.cpp:103:41: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  103 |             filled[i][j] = sz[to(i, j)] = 1;
      |                            ~~~~~~~~~~~~~^~~
joioi.cpp:22:39: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define F(i, l, r) for (ll i = (l); i < r; ++i)
......
  122 |     F(idx, 0, a.size()) {
      |       ~~~~~~~~~~~~~~~~                 
joioi.cpp:122:5: note: in expansion of macro 'F'
  122 |     F(idx, 0, a.size()) {
      |     ^

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40