oj.uz

Submission #1098048

# Submission time Handle Problem Language Result Execution time Memory
1098048 2024-10-09T01:04:11 Z peacebringer1667 The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 1 ms 464 KB 
#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 2e3 + 5;

struct CTDL{
	int x = 0,y = 0,val = 0;
	bool operator <(const CTDL&other) const{
		return (val < other.val);
	}
};

int a[maxn][maxn],Mpos[maxn],mpos[maxn];
vector <CTDL> vec;

int input(int n,int m){
	for (int i = 1 ; i <= n ; i++){
		for (int j = 1 ; j <= m ; j++){
			cin >> a[i][j];
			vec.push_back({i,j,a[i][j]});
		}
	}
	
	sort(vec.begin(),vec.end());
	return vec.back().val - vec[0].val;
}


void refn(int n){
	for (int i = 0 ; i <= n ; i++)
		Mpos[i] = 0;
}
void refm(int n,int m){
	for (int i = 0 ; i <= n ; i++)
	  mpos[i] = m + 1;
}
bool first_left_right(int n,int m,const vector <int> &vm,const vector <int> &VM){
	refn(n);
	for (int x : vm)
	  Mpos[vec[x].x] = max(Mpos[vec[x].x],vec[x].y);
	  
	refm(n,m);
	for (int x : VM)
	  mpos[vec[x].x] = min(mpos[vec[x].x],vec[x].y);
	
	int cur = m + 1;
	for (int i = 1 ; i <= n ; i++){
		if (Mpos[i] > cur) return 0;
		cur = min(cur,mpos[i] - 1);
	}
	
	return 1;
}

void reim(int n,int m){
	for (int i = 0 ; i <= m ; i++) Mpos[i] = 0;
}

void reimn(int n,int m){
	for (int i = 1 ; i <= m ; i++) mpos[i] = n + 1;
}
bool first_hor(int n,int m,const vector <int> &vm,const vector <int> &VM){
	reim(n,m);
	for (int x : vm)
	  Mpos[vec[x].y] = max(Mpos[vec[x].y],vec[x].x);
	
	reimn(n,m);
	for (int x : VM)
	  mpos[vec[x].y] = min(mpos[vec[x].y],vec[x].x);
	
	int cur = n + 1;
	for (int i = 1 ; i <= m ; i++){
		if (Mpos[i] > cur) return 0;
		cur = min(cur,mpos[i] - 1);
	}
	
	return 1;
}

bool first_possible(int n,int m,int h){
	vector <int> ssm,ssM;
	
	for (int i = 0 ; i < vec.size() ; i++)
	  if (vec.back().val - vec[i].val > h)
	    ssm.push_back(i);
	  else break;
	
	for (int i = vec.size() - 1 ; i >= 0 ; i--)
	  if (vec[i].val - vec[0].val > h)
	    ssM.push_back(i);
	  else break;
	
	if (ssm.size() + ssM.size() > vec.size()) return 0;
	//ssm left , ssM right
	return first_left_right(n,m,ssm,ssM) || first_left_right(n,m,ssM,ssm) || first_hor(n,m,ssm,ssM) || first_hor(n,m,ssM,ssm);    
}


bool second_left_right(int n,int m,const vector <int> &vm,const vector <int> VM){
    refn(n);
	for (int x : vm)
	  Mpos[vec[x].x] = max(Mpos[vec[x].x],vec[x].y);
	 
	refm(n,m);
	for (int x : VM)
	  mpos[vec[x].x] = min(mpos[vec[x].x],vec[x].y);
	 
	for (int i = 1 ; i <= n ; i++)
      if (mpos[i] == m + 1) mpos[i] = mpos[i - 1];
	
	int cur = 0; 
	for (int i = 1 ; i <= n ; i++){
        if (mpos[i] < cur) return 0;
        
        cur = max(cur,Mpos[i] + 1);
	}
	return 1;
}

bool second_hor(int n,int m,const vector <int> &vm,const vector <int> &VM){
	reim(n,m);
	for (int x : vm)
	  Mpos[vec[x].y] = max(Mpos[vec[x].y],vec[x].x);
	
	reimn(n,m);
	for (int x : VM)
	  mpos[vec[x].y] = min(mpos[vec[x].y],vec[x].x);
	
	int cur = 0;
	for (int i = 1 ; i <= m ; i++){
		if (mpos[i] < cur) return 0;
		cur = max(cur,Mpos[i] + 1);
	}
	
	return 1;
}

bool second_possible(int n,int m,int h){
	vector <int> ssm,ssM;
	
	for (int i = 0 ; i < vec.size() ; i++)
	  if (vec.back().val - vec[i].val > h)
	    ssm.push_back(i);
	
	for (int i = 0 ; i < vec.size() ; i++)
	  if (vec[i].val - vec[0].val > h)
	    ssM.push_back(i);
	
	if (ssm.size() + ssM.size() > vec.size()) return 0;
	
	return second_left_right(n,m,ssm,ssM) || second_left_right(n,m,ssM,ssm) || second_hor(n,m,ssm,ssM) || second_hor(n,m,ssM,ssm);
}


int solve(int n,int m){
	int range = input(n,m);
	
	int l = 0,r = range,res = 0;
	while (l <= r){
		int w = (l + r)/2;
		if (first_possible(n,m,w) || second_possible(n,m,w)){
			res = w;
			r = w - 1;
		}
		else l = w + 1;
	}
	return res;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int n,m;
	cin >> n >> m;
	cout << solve(n,m);

	return 0;
}

Compilation message

joioi.cpp: In function 'bool first_possible(int, int, int)':
joioi.cpp:89:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<CTDL>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for (int i = 0 ; i < vec.size() ; i++)
      |                   ~~^~~~~~~~~~~~
joioi.cpp: In function 'bool second_possible(int, int, int)':
joioi.cpp:147:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<CTDL>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |  for (int i = 0 ; i < vec.size() ; i++)
      |                   ~~^~~~~~~~~~~~
joioi.cpp:151:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<CTDL>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |  for (int i = 0 ; i < vec.size() ; i++)
      |                   ~~^~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 464 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 464 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 464 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 464 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 464 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 464 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -