답안 #46648 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46648	2018-04-22T13:27:47 Z	Jatana	The Kingdom of JOIOI (JOI17_joioi)	C++17	60 / 100	4000 ms	126384 KB

joioi

/*
                                                                                                     
                                             `-:://:::-                                             
                                           `//:-------:/:`                                          
                                          .+:--.......--:+`                                         
                                         `+:--..`````..--//`                                        
                                         .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+/-.`                                           
                                               ``````                                               
*/

#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;


int solve(vector<vector<int>> v) {
	int n = len(v);
	int m = len(v[0]);
	
	vector<pii> all;	
	f(i, n) {
		f(j, m) {
			all.emplace_back(i, j);
		}
	}
	sort(all.begin(), all.end(), [&v](pii a, pii b) {
		return v[a.x][a.y] < v[b.x][b.y];
	});

	vector<vector<int>> pr_min = v;
	vector<vector<int>> pr_max = v;

	f(i, n) {
		rof(j, m) {
			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, len(all)) {
		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;
}

vector<vector<int>> rotate(vector<vector<int>> v) {
	int n = len(v);
	int m = len(v[0]);
	vector<vector<int>> rez(m, vector<int>(n));
	f(i, n) {
		f(j, m) {
			rez[m - j - 1][i] = v[i][j];
		}
	}
	return rez;
}

signed main(signed argc, char *argv[]) {
	int n, m;
	vector<vector<int>> v;
	{
		scan n, m;
		v.resize(n, vector<int>(m));
		scan v;
	}	
	{
		int rez = 2e9;
		f(t, 5) {
			rez = min(rez, solve(v));
			v = rotate(v);
		}
		print rez;
	}
}

Compilation message

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);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	360 KB	Output is correct
3	Correct	2 ms	416 KB	Output is correct
4	Correct	2 ms	416 KB	Output is correct
5	Correct	2 ms	532 KB	Output is correct
6	Correct	2 ms	628 KB	Output is correct
7	Correct	2 ms	628 KB	Output is correct
8	Correct	2 ms	652 KB	Output is correct
9	Correct	2 ms	660 KB	Output is correct
10	Correct	2 ms	660 KB	Output is correct
11	Correct	2 ms	660 KB	Output is correct
12	Correct	2 ms	660 KB	Output is correct
13	Correct	2 ms	676 KB	Output is correct
14	Correct	2 ms	680 KB	Output is correct

Subtask #2
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	360 KB	Output is correct
3	Correct	2 ms	416 KB	Output is correct
4	Correct	2 ms	416 KB	Output is correct
5	Correct	2 ms	532 KB	Output is correct
6	Correct	2 ms	628 KB	Output is correct
7	Correct	2 ms	628 KB	Output is correct
8	Correct	2 ms	652 KB	Output is correct
9	Correct	2 ms	660 KB	Output is correct
10	Correct	2 ms	660 KB	Output is correct
11	Correct	2 ms	660 KB	Output is correct
12	Correct	2 ms	660 KB	Output is correct
13	Correct	2 ms	676 KB	Output is correct
14	Correct	2 ms	680 KB	Output is correct
15	Correct	3 ms	732 KB	Output is correct
16	Correct	20 ms	1908 KB	Output is correct
17	Correct	38 ms	2280 KB	Output is correct
18	Correct	43 ms	2552 KB	Output is correct
19	Correct	40 ms	2852 KB	Output is correct
20	Correct	33 ms	2984 KB	Output is correct
21	Correct	40 ms	3476 KB	Output is correct
22	Correct	37 ms	3812 KB	Output is correct
23	Correct	39 ms	4300 KB	Output is correct
24	Correct	33 ms	4516 KB	Output is correct
25	Correct	40 ms	5000 KB	Output is correct
26	Correct	43 ms	5384 KB	Output is correct
27	Correct	39 ms	5712 KB	Output is correct
28	Correct	41 ms	6164 KB	Output is correct

Subtask #3
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	360 KB	Output is correct
3	Correct	2 ms	416 KB	Output is correct
4	Correct	2 ms	416 KB	Output is correct
5	Correct	2 ms	532 KB	Output is correct
6	Correct	2 ms	628 KB	Output is correct
7	Correct	2 ms	628 KB	Output is correct
8	Correct	2 ms	652 KB	Output is correct
9	Correct	2 ms	660 KB	Output is correct
10	Correct	2 ms	660 KB	Output is correct
11	Correct	2 ms	660 KB	Output is correct
12	Correct	2 ms	660 KB	Output is correct
13	Correct	2 ms	676 KB	Output is correct
14	Correct	2 ms	680 KB	Output is correct
15	Correct	3 ms	732 KB	Output is correct
16	Correct	20 ms	1908 KB	Output is correct
17	Correct	38 ms	2280 KB	Output is correct
18	Correct	43 ms	2552 KB	Output is correct
19	Correct	40 ms	2852 KB	Output is correct
20	Correct	33 ms	2984 KB	Output is correct
21	Correct	40 ms	3476 KB	Output is correct
22	Correct	37 ms	3812 KB	Output is correct
23	Correct	39 ms	4300 KB	Output is correct
24	Correct	33 ms	4516 KB	Output is correct
25	Correct	40 ms	5000 KB	Output is correct
26	Correct	43 ms	5384 KB	Output is correct
27	Correct	39 ms	5712 KB	Output is correct
28	Correct	41 ms	6164 KB	Output is correct
29	Execution timed out	4019 ms	126384 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

답안 #46648

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 45.0 / 45.0

Subtask #3 0 / 40.0

Subtask #1
15.0 / 15.0

Subtask #2
45.0 / 45.0

Subtask #3
0 / 40.0