Submission #46658

#TimeUsernameProblemLanguageResultExecution timeMemory
46658JatanaThe Kingdom of JOIOI (JOI17_joioi)C++17
100 / 100
3427 ms167368 KiB
/* `-:://:::- `//:-------:/:` .+:--.......--:+` `+:--..`````..--//` .o:--..`` ``..--:o` .o:--...```..---+/` `/y+o/---....---:+o. `...````-os+/:---:/+o/--.` `-/+++++/:. `...` :h+d+oooo+/+-` ... `/++//:::://++-`....` -.`//````````:` `..` `o+/::------://o/` `-` -. -` `..` `---.-o/:./o/::-..``..-ЗАПУСКАЕМ .. .. -` `... ``..`` `....o+:-++/:--.```..-://s. `-` .- -` `-o: .-//::::/:-` `:s+/:--....-::/+s-` .- `- -` -///:--------:/:` ./s+//:::::://oo-``..НЕЙРОННУЮ: СЕТЬ:::::::-`РАБОТЯГИ `+:--........--:/` .:ooo+++++osso-` `.:-...`/` ./::-------:/:` -` :+--..``````.--:+:...-+:-` `.-/+++++/+-.-` -. ``:so:/:--.......--:+` `-```````o+/+--..`````..--:o/-..:s+:. ```````:``.. `-` -` `+:--..`````..--/+-.../.`````..-o:--.......---/o. ` `: `:- -. .o:--..`` ``..--:o` `-` `:o+:--------:+o-` `-`-... .. .o/--...```..--:+/` `-` `oy/so/////++o/.` -/` `-` `- ``+s/o/:---...---:++. `-` .-../d://///:-.` `.---..``-..- .-/..`````-oo+/:::::/+o+- `-``-` `-. ```` `:++++/+++++- ..``.-/:` /y-:/++o++/:.`..` ./. `- -++/::::::://+/..:-``:` .. `-.` ```.``` `..` `..`-` `- `` -o//:--....-::/++` -.-` `-`.-` `..`..` `-.- -----ss+:++/:--.```..-://s. /. `:: `-:. ./` `````/:..+o/::-..``.--:/+s. ..-` `-``-` ..` `-` `-`-` `-s+/::-----::/+oo---``-` .. .:- ``` .-` .-.- `-` `:oo+//::://+os/..:`..-/:` :y.-:::::::.`.-` ./-` `-` `./+oooooooo+/.`- .-:...`.. .//:-------://` `- `..` `:. ``.-::::-.``-/` `-` `- `oo:+:--.......--:/` `- `.:--h.``..``` -.-`.- .- `+:--..`````..--//` `- /s-//::::::::. -` `/- .. .o:--..`` ``..--:o.```.- `//:--------://` -` .-`.-` -.`-o/--...```..--:+/.``-:....``:-.+:--....`...--:+` ..`-. `-. ``:os:o/:---...---:++. `- ``///+:-..``````.--:+-````-.` `.:///////.-` .:-..` -``-+o+/:::::/+o/. `- `:+:-..`````..--:o/:--/ys+- `-++///////+o/. ``....`-. :` `.:++++++/:.` .- -o/---......---/o. `.` `++//:-----::/+o:..` .-` : ``````` .- `+so+:--------:++-` `````:-``:o/::-..`..--:/+o` -. `- .- `../../+o+////+o+:.` -----syo/o+/:--.```..-://s. .-` `- .- `... ``-:////:-`` .` `/s//:--....-::/+s. -. `-` .- `..` .+o+/:::--:://+s/-..` .::+y ``` .- `..` ./oo++////+oso-` `.... :y-+:::::::/` ... `.:+oooooo/-` `....-. .//:-------:/:-.` ``...`` /+:+:--.......--:+` `+:--..`````..--//` .o:--..`` ``..--:o` .+/--...```..--:+/` `-o/:---...---:++. `-+o+/:---:/+o/. `.:+oooo+/-.` `````` */ // #define aimbot #ifdef aimbot #pragma comment(linker, "/stack:200000000") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma GCC optimize("unroll-loops") #endif #include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <string> #include <unordered_map> #include <unordered_set> #include <map> #include <set> #include <queue> #include <ostream> #include <istream> #include <typeinfo> #include <iomanip> #include <cstdio> #include <cstdlib> #include <cassert> #include <limits> #include <fstream> #include <array> #include <list> #include <bitset> #include <functional> #include <random> #include <cstring> #define mt make_tuple #define x first #define y second #define pb push_back #define ppb pop_back #define mp make_pair #define umap unordered_map #define uset unordered_set #define elif else if #define len(v) ((int)v.size()) #define f(i, n) for (int i = 0; i < (n); i++) #define rof(i, n) for (int i = ((n) - 1); i >= 0; i--) #define apply(v, act) for (auto &x : v) { act; } #define fuck(args...) {string s = #args;deque<string> deq;\ string buf = "";int bal = 0;for (char c : s) {\ if (c == '(' || c == '[' || c == '{') {bal++;\ } else if (c == ')' || c == ']' || c == '}') {\ bal--;} else {if (bal == 0) {if (c == ',') {\ deq.pb(buf);buf = "";} else {if (c != ' ') {\ buf += c;}}}}}if (!buf.empty()) {deq.pb(buf);}\ smart_io::precall_print();smart_io::_print(deq, args);} #define print \ smart_io::precall_print(); \ cout, #define scan cin, #ifdef fast_allocator const int MAXMEM = 50000000; char _memory[MAXMEM]; size_t _ptr = 0; void* operator new(size_t _x) { _ptr += _x; assert(_ptr < MAXMEM); return _memory + _ptr - _x; } void operator delete (void*) noexcept {} #endif using namespace std; char string_in_buffer[(int)260]; void fast_scan(int &x) { scanf("%d", &x); } void fast_scan(long long &x) { scanf("%lld", &x); } void fast_scan(unsigned long long &x) { scanf("%llu", &x); } void fast_scan(double &x) { scanf("%lf", &x); } void fast_scan(long double &x) { scanf("%Lf", &x); } void fast_scan(char &x) { scanf("%c", &x); if (x == '\n') { fast_scan(x); } } void fast_scan(string &x) { scanf("%s", string_in_buffer); x = string(string_in_buffer); } template<class TFirst, class TSecond> void fast_scan(pair<TFirst, TSecond> &p) { fast_scan(p.first); fast_scan(p.second); } template <class T> void fast_scan(vector<T> &v) { for (auto &x : v) fast_scan(x); } void fast_print(const int &x) { printf("%d", x); } void fast_print(const long long &x) { printf("%lld", x); } void fast_print(const unsigned long long &x) { printf("%llu", x); } void fast_print(const double &x) { printf("%.15lf", x); } void fast_print(const long double &x) { printf("%.15Lf", x); } void fast_print(const char &x) { printf("%c", x); }; void fast_print(const string &x) { printf("%s", x.c_str());} void fast_print(const char v[]) { fast_print((string)v); } template<class TFirst, class TSecond> void fast_print(const pair<TFirst, TSecond> &p) { fast_print(p.first); fast_print(' '); fast_print(p.second); } template <class T> void fast_print(const vector<T> &v) { if (v.empty()) return; fast_print(v[0]); for (int i = 1; i < v.size(); i++) { fast_print(' '); fast_print(v[i]); } } template <class T> void fast_print(const vector<vector<T>> &v) { if (v.empty()) return; fast_print(v[0]); for (int i = 1; i < v.size(); i++) { fast_print('\n'); fast_print(v[i]); } } template <class T> void fast_print(const T &v) { for (const auto &x : v) { fast_print(x); fast_print(' '); } } using namespace std; namespace smart_io { string print_start = ""; string sep = " "; bool first_print = false; void precall_print() { fast_print(print_start); print_start = "\n"; first_print = true; } void _print(deque<string>) {} template<class T, class... Args> void _print(deque<string> names, T kek, Args... args) { if (!first_print) { fast_print("\n"); } else { first_print = false; } fast_print(names.front()); fast_print(" = "); fast_print(kek); names.pop_front(); _print(names, args...); } } //namespace smart_io template <class T> ostream &operator,(ostream &os, const T &object) { if (!smart_io::first_print) { fast_print(smart_io::sep); } else { smart_io::first_print = false; } fast_print(object); return os; } template <class T> istream &operator,(istream &is, T &object) { fast_scan(object); return is; } namespace typedefs { typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef long double ld; } namespace numbers_operation { template<class T> T floor_mod(T a, T b) { if (a % b == 0) return 0; if (a >= 0 && b >= 0) return a % b; if (a <= 0 && b <= 0) return a % b; return abs(b) - (abs(a) % abs(b)); } } using namespace numbers_operation; using namespace typedefs; const int N = 2000; int v[N][N]; int rez[N][N]; int pr_min[N][N]; int pr_max[N][N]; pii all[N * N]; int solve(int n, int m) { f(i, n) { rof(j, m) { pr_min[i][j] = pr_max[i][j] = v[i][j]; if (i > 0) { pr_min[i][j] = min(pr_min[i][j], pr_min[i - 1][j]); pr_max[i][j] = max(pr_max[i][j], pr_max[i - 1][j]); } if (j < m - 1) { pr_min[i][j] = min(pr_min[i][j], pr_min[i][j + 1]); pr_max[i][j] = max(pr_max[i][j], pr_max[i][j + 1]); } } } int left = 2e9, right = -2e9; int rez = 2e9; rof(i, n * m) { left = min(left, pr_min[all[i].x][all[i].y]); right = max(right, pr_max[all[i].x][all[i].y]); int d = (i == 0) ? 0 : v[all[i - 1].x][all[i - 1].y] - v[all[0].x][all[0].y]; rez = min(rez, max(right - left, d)); } return rez; } void rotate(int n, int m) { f(i, n) { f(j, m) { rez[m - j - 1][i] = v[i][j]; } } f(i, n) { f(j, m) { v[j][i] = rez[j][i]; } } f(i, n * m) { pii &p = all[i]; tie(p.x, p.y) = mp(m - p.y - 1, p.x); } } signed main(signed argc, char *argv[]) { int n, m; { scan n, m; f(i, n) { f(j, m) { scan v[i][j]; } } } { int it = 0; f(i, n) { f(j, m) { all[it++] = mp(i, j); } } sort(all, all + n * m, [](const pii &a, const pii &b) { return v[a.x][a.y] < v[b.x][b.y]; }); } { int rez = 2e9; f(t, 4) { rez = min(rez, solve(n, m)); rotate(n, m); swap(n, m); } print rez; } }

Compilation message (stderr)

joioi.cpp: In function 'void fast_scan(int&)':
joioi.cpp:131:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void fast_scan(int &x) { scanf("%d", &x); }
                          ~~~~~^~~~~~~~~~
joioi.cpp: In function 'void fast_scan(long long int&)':
joioi.cpp:132:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void fast_scan(long long &x) { scanf("%lld", &x); }
                                ~~~~~^~~~~~~~~~~~
joioi.cpp: In function 'void fast_scan(long long unsigned int&)':
joioi.cpp:133:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void fast_scan(unsigned long long &x) { scanf("%llu", &x); }
                                         ~~~~~^~~~~~~~~~~~
joioi.cpp: In function 'void fast_scan(double&)':
joioi.cpp:134:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void fast_scan(double &x) { scanf("%lf", &x); }
                             ~~~~~^~~~~~~~~~~
joioi.cpp: In function 'void fast_scan(long double&)':
joioi.cpp:135:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void fast_scan(long double &x) { scanf("%Lf", &x); }
                                  ~~~~~^~~~~~~~~~~
joioi.cpp: In function 'void fast_scan(char&)':
joioi.cpp:137:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%c", &x); 
  ~~~~~^~~~~~~~~~
joioi.cpp: In function 'void fast_scan(std::__cxx11::string&)':
joioi.cpp:143:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", string_in_buffer);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...