Untitled

mail@pastecode.io avatar
unknown
plain_text
4 days ago
3.5 kB
2
Indexable
Never
#pragma warning(disable : 4996)
#include <iostream>
#include <vector>
#include <string.h>
#include <string>
#include <math.h>
#include <map>
#include <set>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include<iterator> 
#include <queue>
#include<cstdlib>
using namespace std;
typedef long long ll;
typedef vector<vector<int>> matrix;
#define f(x,y) for(ll x=0;x<y;x++)
#define ff(x,z,y) for(ll x=z;x<y;x++)
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define print(x) cout<<x
#define println2(x) cout<<"out: "<<x<<endl
#define println(x) cout<<x<<endl
#define is_odd(x) (x%2!=0)
#define FIO	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define all(v) v.begin(),v.end()
#define sortv(v) sort(all(v))
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvvi vector<vector<vector<int>>>
#define vvvl vector<vector<vector<ll>>>
const int N = 1e5;
ll n, m;
vvl hei, gold;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
vector<vector<int>>visit;
bool valid(int i, int j) {
	bool vla = i >= 0 and i < n&& j >= 0 and j < m;
	return vla;
}
void dfs(int i, int j, ll par_heig, int cluster) {
	if (!valid(i, j) or visit[i][j] != -1)return;
	if (par_heig != -1 && (par_heig > hei[i][j] * 1.5 || hei[i][j] > par_heig * 1.5))
		return;
	visit[i][j] = cluster;
	for (int index = 0; index < 4; index++) {
		dfs(i + dx[index], j + dy[index], hei[i][j], cluster);
	}
}
int solve() {
	visit = vector<vector<int>>(n, vector<int>(m, -1));
	int latest = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visit[i][j] == -1) {
				dfs(i, j, -1, latest);
				latest++;
			}
		}
	}
	vector<ll>ids(latest);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			ids[visit[i][j]] += gold[i][j];
		}
	}
	vector<pair<ll, ll>>combines(n * m);
	int index = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			combines[index++] = { hei[i][j],gold[i][j] };
		}
	}
	sort(combines.begin(), combines.end());
	ll count = combines[0].second/2;
	index = 1;
	vector<ll >ends;
	vector<ll>values;
	while (index < n * m)
	{
		if (combines[index].first > 1.5 * combines[index - 1].first) {
			ends.push_back(combines[index - 1].first);
			values.push_back(count);
			count = 0;
		}
		count += combines[index].second/2;
		index++;
	}
	ends.push_back(combines[n * m - 1].first);
	values.push_back(count);

	ll player1 = 0, player2 = 0;
	for (int i = 0; i < n / 2; i++) {
		for (int j = 0; j < m; j++) {
			int it = lower_bound(ends.begin(), ends.end(), hei[i][j]) - ends.begin();
			player1 = max(player1, max(ids[visit[i][j]], values[it]));
		}
	}
	for (int i = n / 2; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int it = lower_bound(ends.begin(), ends.end(), hei[i][j]) - ends.begin();
			player2 = max(player2, max(ids[visit[i][j]], values[it]));

		}
	}
	if (player1 > player2)
		return 1;
	else if (player2 > player1)
		return 2;
	else
		return 0;
}
void read() {
	cin >> n >> m;
	hei = vector<vector<ll>>(n, vector<ll>(m, 0));
	gold = vector<vector<ll>>(n, vector<ll>(m, 0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> hei[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> gold[i][j];
		}
	}
}

int main(int argc, char* argv[])
{
	read();
	int sol = solve();
	println(sol);
}
Leave a Comment