oj.uz

Submission #145665

# Submission time Handle Problem Language Result Execution time Memory
145665 2019-08-20T17:59:49 Z TadijaSebez The Kingdom of JOIOI (JOI17_joioi) C++11
60 / 100
 4000 ms 162232 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=2050;
int n,m,a[N][N];
multiset<int> JOI,IOI;
vector<pair<int,int>> ord;
int ans=-1;
bool was[N][N];
void Upd()
{
	if(JOI.empty() || IOI.empty()) return;
	int tmp=max(*JOI.rbegin()-*JOI.begin(),*IOI.rbegin()-*IOI.begin());
	if(ans==-1 || ans>tmp) ans=tmp;
}
void Solve(vector<pair<int,int>> Move)
{
	JOI.clear();
	IOI.clear();
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) IOI.insert(a[i][j]),was[i][j]=0;
	for(auto p:ord)
	{
		int x,y;
		tie(x,y)=p;
		if(!was[x][y])
		{
			queue<pair<int,int>> q;
			auto push=[&](int i, int j)
			{
				q.push({i,j});
				was[i][j]=1;
				IOI.erase(IOI.find(a[i][j]));
				JOI.insert(a[i][j]);
			};
			push(x,y);
			while(q.size())
			{
				tie(x,y)=q.front();
				q.pop();
				for(auto mv:Move)
				{
					int nx,ny;
					nx=x+mv.first;
					ny=y+mv.second;
					if(nx>=1 && nx<=n && ny>=1 && ny<=m && !was[nx][ny]) push(nx,ny);
				}
			}
		}
		Upd();
	}
}
int main()
{
	scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%i",&a[i][j]),ord.pb({i,j});
	sort(ord.begin(),ord.end(),[&](pair<int,int> x, pair<int,int> y){ return a[x.first][x.second]>a[y.first][y.second];});
	Solve({{-1,0},{0,-1}});
	Solve({{-1,0},{0,1}});
	Solve({{1,0},{0,-1}});
	Solve({{1,0},{0,1}});
	printf("%i\n",ans);
	return 0;
}

Compilation message

joioi.cpp: In function 'int main()':
joioi.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
joioi.cpp:55:66: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%i",&a[i][j]),ord.pb({i,j});
                                              ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 6 ms 760 KB Output is correct
16 Correct 113 ms 3948 KB Output is correct
17 Correct 182 ms 4348 KB Output is correct
18 Correct 173 ms 4336 KB Output is correct
19 Correct 174 ms 4332 KB Output is correct
20 Correct 160 ms 3824 KB Output is correct
21 Correct 190 ms 4336 KB Output is correct
22 Correct 179 ms 4336 KB Output is correct
23 Correct 176 ms 4464 KB Output is correct
24 Correct 147 ms 4040 KB Output is correct
25 Correct 179 ms 4436 KB Output is correct
26 Correct 187 ms 4436 KB Output is correct
27 Correct 182 ms 4436 KB Output is correct
28 Correct 183 ms 4336 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 6 ms 760 KB Output is correct
16 Correct 113 ms 3948 KB Output is correct
17 Correct 182 ms 4348 KB Output is correct
18 Correct 173 ms 4336 KB Output is correct
19 Correct 174 ms 4332 KB Output is correct
20 Correct 160 ms 3824 KB Output is correct
21 Correct 190 ms 4336 KB Output is correct
22 Correct 179 ms 4336 KB Output is correct
23 Correct 176 ms 4464 KB Output is correct
24 Correct 147 ms 4040 KB Output is correct
25 Correct 179 ms 4436 KB Output is correct
26 Correct 187 ms 4436 KB Output is correct
27 Correct 182 ms 4436 KB Output is correct
28 Correct 183 ms 4336 KB Output is correct
29 Execution timed out 4021 ms 162232 KB Time limit exceeded
30 Halted 0 ms 0 KB -