oj.uz

Submission #46711

# Submission time Handle Problem Language Result Execution time Memory
46711 2018-04-22T15:34:00 Z golub The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 2 ms 596 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,sse4")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("unroll-all-loops")

#include <bits/stdc++.h>

//#define TASK "lca"

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define F first
#define S second
#define pb push_back
#define int long long
#define pii pair<int, int>

typedef long long ll;
//typedef long double ld;

using namespace std;

const int INF = 1e18;
const int MAXN = 1e8;
const int MOD = 1e9 + 7;
const double EPS = 1e-12;

const vector<int> dx = {1, 0, -1, 0, 0, 1, 0, -1};

//char buf[(int)1e9];
//size_t p_ = 0;
//
//inline void *operator new(size_t n_) {
//    p_ += n_;
//    return buf + p_ - n_;
//}
//inline void operator delete(void*) {};

ll power(ll x, ll n, ll mod = 1e9 + 7) {
    if (n == 0) return 1ll;
    if (n & 1ll) return power(x, n - 1ll, mod) * x % mod;
    ll tmp = power(x, n >> 1ll, mod);
    return (tmp * tmp) % mod;
}

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd (b, a % b);
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

int n, m;
map<pii, bool> used;
vector<vector<int>> g;

void go(pii p, set<pair<int, pii>> &next) {
    for (int i = 0; i < 4; i++) {
        int x = p.F + dx[i * 2];
        int y = p.S + dx[i * 2 + 1];
        if (x < 0 || x >= n || y < 0 || y >= m) continue;
        if (!used[{x, y}]) {
            next.insert({g[x][y], {x, y}});
        }
    }
}

signed main() {
#ifndef LOCAL
#ifdef TASK
    freopen(TASK".in", "r", stdin);
    freopen(TASK".out", "w", stdout);
#endif
#endif
#ifdef LOCAL
    //freopen("/Users/alekseygolub/Desktop/с++/ABS/ABS/input.txt", "r", stdin);
#endif
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(924653523);
    // == SOLUTION == //
    cin >> n >> m;
    int MIN = INF;
    pii pos_min;
    int MAX = -INF;
    pii pos_max;
    g.resize(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
            if (g[i][j] < MIN) {
                MIN = g[i][j];
                pos_min = {i, j};
            }
            if (g[i][j] > MAX) {
                MAX = g[i][j];
                pos_max = {i, j};
            }
        }
    }
    int ans1 = 0;
    int ans2 = 0;
    set<pii> side_a, side_b;
    side_a.insert(pos_min);
    side_b.insert(pos_max);
    used[pos_max] = 1;
    used[pos_min] = 1;
    set<pair<int, pii>> next_a, next_b;
    go(pos_max, next_b);
    go(pos_min, next_a);
    while(side_a.size() + side_b.size() != n * m) {
        while (!next_a.empty() && used[(*next_a.begin()).S]) next_a.erase(next_a.begin());
        while (!next_b.empty() && used[(*next_b.rbegin()).S]) next_b.erase(*next_b.rbegin());
        if (next_a.empty() || next_b.empty()) break;
        
        int test1 = max(ans1, abs(MIN - (*next_a.begin()).F));
        int test2 = max(ans2, abs(MAX - (*next_b.rbegin()).F));
        
        if (test1 < test2) {
            ans1 = test1;
            pii p = (*next_a.begin()).S;
            side_a.insert(p);
            used[p] = 1;
            next_a.erase(next_a.begin());
            go(p, next_a);
        } else {
            ans2 = test2;
            pii p = (*next_b.rbegin()).S;
            side_b.insert(p);
            used[p] = 1;
            next_b.erase(*next_b.rbegin());
            go(p, next_b);
        }
    }
    
    if (side_a.size() + side_b.size() != n * m && next_a.size()) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!used[{i, j}]) {
                    side_a.insert({i, j});
                    used[{i, j}] = 1;
                }
            }
        }
    }

    if (side_a.size() + side_b.size() != n * m && next_b.size()) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!used[{i, j}]) {
                    side_b.insert({i, j});
                    used[{i, j}] = 1;
                }
            }
        }
    }
    
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < m; j++) {
//            if (j != 0) cout << " ";
//            if (used[{i, j}] && side_a.count({i, j})) cout << "1 ";
//            if (used[{i, j}] && side_b.count({i, j})) cout << "2 ";
//            if (!used[{i, j}]) cout << "- ";
//        }
//        cout << "\n";
//    }
    
    for (auto p: side_a) {
        ans1 = max(ans1, abs(MIN - g[p.F][p.S]));
        used[p] = 0;
    }
    next_b.clear();
    for (auto p: side_b) {
        ans2 = max(ans2, abs(MAX - g[p.F][p.S]));\
        go(p, next_b);
    }
    while (!next_b.empty()) {
        while (!next_b.empty() && max(ans1, ans2) < abs(MAX - (*next_b.begin()).F)) next_b.erase(next_b.begin());
        if (next_b.empty()) break;
        auto u = *next_b.begin();
        side_b.insert(u.S);
        side_a.erase(u.S);
        used[u.S] = 1;
        next_b.erase(next_b.begin());
        go(u.S, next_b);
    }
//    cout << "\n";
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < m; j++) {
//                if (j != 0) cout << " ";
//                if (used[{i, j}] && side_a.count({i, j})) cout << "1 ";
//                if (used[{i, j}] && side_b.count({i, j})) cout << "2 ";
//                if (!used[{i, j}]) cout << "- ";
//            }
//            cout << "\n";
//        }
//
    ans1 = -INF;
    ans2 = -INF;
    for (auto p: side_a) {
        ans1 = max(ans1, abs(MIN - g[p.F][p.S]));
        //used[p] = 0;
    }
    next_b.clear();
    for (auto p: side_b) {
        ans2 = max(ans2, abs(MAX - g[p.F][p.S]));\
        //go(p, next_b);
    }
    cout << max(ans1, ans2) << '\n';
    
}

Compilation message

joioi.cpp: In function 'int main()':
joioi.cpp:114:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(side_a.size() + side_b.size() != n * m) {
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
joioi.cpp:139:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (side_a.size() + side_b.size() != n * m && next_a.size()) {
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
joioi.cpp:150:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (side_a.size() + side_b.size() != n * m && next_b.size()) {
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 2 ms 408 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Incorrect 2 ms 596 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 2 ms 408 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Incorrect 2 ms 596 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 2 ms 408 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Incorrect 2 ms 596 KB Output isn't correct
8 Halted 0 ms 0 KB -