Submission #648140

#TimeUsernameProblemLanguageResultExecution timeMemory
648140ghostwriterThe Kingdom of JOIOI (JOI17_joioi)C++14
100 / 100
956 ms16136 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include <debug.h> #else #define debug(...) #endif #define ft front #define bk back #define st first #define nd second #define ins insert #define ers erase #define pb push_back #define pf push_front #define _pb pop_back #define _pf pop_front #define lb lower_bound #define ub upper_bound #define mtp make_tuple #define bg begin #define ed end #define all(x) (x).bg(), (x).ed() #define sz(x) (int)(x).size() typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; typedef pair<int, int> pi; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll; typedef string str; template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); } template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; } #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i)) #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i)) #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i)) #define FSN(i, n) for (int (i) = (n) - 1; (i) >= 0; --(i)) #define EACH(i, x) for (auto &(i) : (x)) #define WHILE while #define file "TEST" mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); } /* ---------------------------------------------------------------- END OF TEMPLATE ---------------------------------------------------------------- Tran The Bao - ghostwriter Training for VOI23 gold medal ---------------------------------------------------------------- DIT ME CHUYEN BAO LOC ---------------------------------------------------------------- */ const int oo = 1e9 + 5; const int N = 2e3 + 1; int h, w, a[N][N], mx = 0, my = 0; bool check(int x) { int len = w, minv = oo, maxv = -oo; FOS(i, h, 1) { int j = 1, clen = len; WHILE(a[mx][my] - a[i][j] <= x && clen--) ++j; --j; FOR(z, j + 1, w) { minv = min(minv, a[i][z]); maxv = max(maxv, a[i][z]); } len = j; } if (minv == oo || maxv - minv <= x) return 1; len = w; minv = oo; maxv = -oo; FOR(i, 1, h) { int j = 1, clen = len; WHILE(a[mx][my] - a[i][j] <= x && clen--) ++j; --j; FOR(z, j + 1, w) { minv = min(minv, a[i][z]); maxv = max(maxv, a[i][z]); } len = j; } if (minv == oo || maxv - minv <= x) return 1; len = w; minv = oo; maxv = -oo; FOS(i, h, 1) { int j = w, clen = len; WHILE(a[mx][my] - a[i][j] <= x && clen--) --j; ++j; FOR(z, 1, j - 1) { minv = min(minv, a[i][z]); maxv = max(maxv, a[i][z]); } len = w - j + 1; } if (minv == oo || maxv - minv <= x) return 1; len = w; minv = oo; maxv = -oo; FOR(i, 1, h) { int j = w, clen = len; WHILE(a[mx][my] - a[i][j] <= x && clen--) --j; ++j; FOR(z, 1, j - 1) { minv = min(minv, a[i][z]); maxv = max(maxv, a[i][z]); } len = w - j + 1; } if (minv == oo || maxv - minv <= x) return 1; return 0; } signed main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); // freopen(file".inp", "r", stdin); // freopen(file".out", "w", stdout); cin >> h >> w; FOR(i, 1, h) FOR(j, 1, w) cin >> a[i][j]; FOR(i, 1, h) FOR(j, 1, w) if (a[i][j] > a[mx][my]) tie(mx, my) = mtp(i, j); int l = 0, r = 1e9 - 1, ans = -1; WHILE(l <= r) { int mid = l + (r - l) / 2; if (check(mid)) { ans = mid; r = mid - 1; } else l = mid + 1; } cout << ans; return 0; } /* 8 6 23 23 10 11 16 21 15 26 19 28 19 20 25 26 28 16 15 11 11 8 19 11 15 24 14 19 15 14 24 11 10 8 11 7 6 14 23 5 19 23 17 17 18 11 21 14 20 16 ---------------------------------------------------------------- From Benq: stuff you should look for * int overflow, array bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH ---------------------------------------------------------------- */

Compilation message (stderr)

joioi.cpp: In function 'bool check(int)':
joioi.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   33 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
      |                               ^
joioi.cpp:56:2: note: in expansion of macro 'FOS'
   56 |  FOS(i, h, 1) {
      |  ^~~
joioi.cpp:32:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
joioi.cpp:60:3: note: in expansion of macro 'FOR'
   60 |   FOR(z, j + 1, w) {
      |   ^~~
joioi.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
joioi.cpp:68:2: note: in expansion of macro 'FOR'
   68 |  FOR(i, 1, h) {
      |  ^~~
joioi.cpp:32:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
joioi.cpp:72:3: note: in expansion of macro 'FOR'
   72 |   FOR(z, j + 1, w) {
      |   ^~~
joioi.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   33 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
      |                               ^
joioi.cpp:80:2: note: in expansion of macro 'FOS'
   80 |  FOS(i, h, 1) {
      |  ^~~
joioi.cpp:32:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
joioi.cpp:84:3: note: in expansion of macro 'FOR'
   84 |   FOR(z, 1, j - 1) {
      |   ^~~
joioi.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
joioi.cpp:92:2: note: in expansion of macro 'FOR'
   92 |  FOR(i, 1, h) {
      |  ^~~
joioi.cpp:32:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
joioi.cpp:96:3: note: in expansion of macro 'FOR'
   96 |   FOR(z, 1, j - 1) {
      |   ^~~
joioi.cpp: In function 'int main()':
joioi.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
joioi.cpp:110:5: note: in expansion of macro 'FOR'
  110 |     FOR(i, 1, h)
      |     ^~~
joioi.cpp:32:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
joioi.cpp:111:5: note: in expansion of macro 'FOR'
  111 |     FOR(j, 1, w)
      |     ^~~
joioi.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
joioi.cpp:113:5: note: in expansion of macro 'FOR'
  113 |     FOR(i, 1, h)
      |     ^~~
joioi.cpp:32:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
joioi.cpp:114:5: note: in expansion of macro 'FOR'
  114 |     FOR(j, 1, w)
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...