Submission #639117

#	Time	Username	Problem	Language	Result	Execution time	Memory
639117		minhcool	Hexagonal Territory (APIO21_hexagon)	C++17	0 / 100	1355 ms	61844 KiB

hexagon

#include<bits/stdc++.h>
using namespace std;

//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)

typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef pair<ii, ii> iiii;

const int N = 6e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

ll n, a, b;

int x[] = {-1, -1, 0, 1, 1, 0};
int y[] = {-1, 0, 1, 1, 0, -1};

//vector<int> 

vector<ll> pos[N];

vector<ii> cells;

bool inside[N];

ll dist(ll x, ll y){
	if(x < 0){
		x = -x, y = -y;
	}
	if(y > 0) return max(x, y);
	else return x + (-y);
}

map<ii, int> mp;

int draw_territory(int N, int A, int B, vector<int> D, vector<int> L){
	ii itr = {300000, 300000};
	n = N, a = A, b = B;
	for(int i = 0; i < n; i++){
		D[i]--;
		for(int j = 0; j < L[i]; j++){
			int tempx = itr.fi + x[D[i]] * j, tempy = itr.se + y[D[i]] * j;
			cout << tempx << " " << tempy << "\n";
			pos[tempx].pb(cells.size());
			cells.pb({tempx, tempy});
		}
		itr.fi += x[D[i]] * L[i];
		itr.se += y[D[i]] * L[i];
	}
	for(int i = 0; i <= 600000; i++){
		if(!pos[i].size()) continue;
		ll mx = -oo, mn = oo;
		for(auto it : pos[i]){
			mn = min(mn, cells[it].se);
			mx = max(mx, cells[it].se);
		}
		for(int j = mn; j <= mx; j++) inside[j] = 0;
		for(int j = 1; j < pos[i].size(); j++){
			int temp1 = cells[pos[i][j]].se, temp2 = cells[pos[i][j - 1]].se;
			if(abs(temp1 - temp2) == 1) continue;
			bool ck1 = (temp1 > temp2), ck2 = (cells[pos[i][j] - 1].fi < cells[pos[i][j]].fi);
			if(!(ck1 ^ ck2)) for(int k = min(temp1, temp2); k <= max(temp1, temp2); k++) inside[k] = 1;
			else for(int k = min(temp1, temp2); k <= max(temp1, temp2); k++) inside[k] = 0;
		}
		for(auto it : pos[i]) inside[cells[it].se] = 1;
		cout << i - 300000 << " ";
		for(int j = mn; j <= mx; j++){
			if(inside[j]){
				cout << j - 300000 <<  " ";
				//in_cell.pb({i, j});
				mp[{i - 300000, j - 300000}] = -1;
				//answer %= mod;
			}
		}
		cout << "\n";
	}
	ll answer = 0;
	queue<ii> q;
	mp[{0, 0}] = 0;
	q.push({0, 0});
	while(!q.empty()){
		ii u = q.front();
		cout << u.fi << " " << u.se << " " << mp[u] << "\n";
		q.pop();
		answer += b * mp[u] + a;
		for(int i = 0; i < 6; i++){
			int tempx = u.fi + x[i], tempy = u.se + y[i];
			if(mp.find({tempx, tempy}) == mp.end() || mp[{tempx, tempy}] >= 0) continue;
			mp[{tempx, tempy}] = mp[u] + 1;
			q.push({tempx, tempy});
		}
	}
	//sort(in_cell.begin(), in_cell.end(), )
	int ans = answer;
	return ans;
}
/*
void process(){
	int n, a, b;
	cin >> n >> a >> b;
	vector<int> d, l;
	for(int i = 0; i < n; i++){
		int x, y;
		cin >> x >> y;
		d.pb(x), l.pb(y);
	}
	cout << draw_territory(n, a, b, d, l) << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	process();
}
*/

Compilation message (stderr)

hexagon.cpp:19:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   19 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
hexagon.cpp: In function 'int draw_territory(int, int, int, std::vector<int>, std::vector<int>)':
hexagon.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(int j = 1; j < pos[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 15
• Subtask 6: 0 / 19
• Subtask 7: 0 / 18
• Subtask 8: 0 / 16