Submission #36078

#	Time	Username	Problem	Language	Result	Execution time	Memory
36078		DoanPhuDuc	The Kingdom of JOIOI (JOI17_joioi)	C++98	100 / 100	1606 ms	80924 KiB

joioi

#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }

using namespace std;

typedef long long LL;

const int N = 2e3 + 10;
const int INF = 0x3f3f3f3f;

int n, m, minV = INF, maxV = -INF, nn, mm;
int a[N][N], b[4][N][N], NN[4], MM[4];

void Rotate(int x, int y) {
    int nn = NN[x], mm = MM[x];
    FOR(i, 1, nn)
        FOR(j, 1, mm) b[y][j][i] = b[x][nn - i + 1][j];
    NN[y] = mm; MM[y] = nn;
}

void Init() {
    NN[0] = n; MM[0] = m;
    FOR(i, 1, NN[0])
        FOR(j, 1, MM[0]) b[0][i][j] = a[i][j];
    Rotate(0, 1);
    Rotate(1, 2);
    Rotate(2, 3);
}

bool Greedy(int t, int diff) {
    nn = NN[t], mm = MM[t];
    int l = minV, r = l + diff;
    vector <int> f;
    int p = mm;
    FOR(i, 1, nn) {
        FOR(j, 1, p) {
            if (l <= b[t][i][j] && b[t][i][j] <= r) continue;
            p = j - 1;
            break;
        }
        f.push_back(p);
    }
    int x = INF, y = -INF;
    FOR(i, 1, nn) {
        int p = f[i - 1];
        FOR(j, p + 1, mm) {
            x = min(x, b[t][i][j]);
            y = max(y, b[t][i][j]);
        }
    }
    if (x == INF) return true;
        else return abs(x - y) <= diff;
}

bool Check(int diff) {
    if (Greedy(0, diff) == true) return true;
    if (Greedy(1, diff) == true) return true;
    if (Greedy(2, diff) == true) return true;
    if (Greedy(3, diff) == true) return true;
    return false;
}

int main() {
   // freopen("KUTO.INP", "r", stdin);
   // freopen("KUTO.OUT", "w", stdout);
    scanf("%d%d", &n, &m);
    FOR(i, 1, n)
        FOR(j, 1, m) scanf("%d", &a[i][j]);
    FOR(i, 1, n)
        FOR(j, 1, m) {
            minV = min(minV, a[i][j]);
            maxV = max(maxV, a[i][j]);
        }
    Init();
    int l = 0, r = maxV - minV, f = -1;
    while (l <= r) {
        int m = (l + r) >> 1;
        if (Check(m)) {
            r = m - 1;
            f = m;
        } else l = m + 1;
    }
    printf("%d", f);
    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:72:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
                          ^
joioi.cpp:74:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         FOR(j, 1, m) scanf("%d", &a[i][j]);
                                           ^

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