oj.uz

Submission #979737

# Submission time Handle Problem Language Result Execution time Memory
979737 2024-05-11T10:38:18 Z c2zi6 Hexagonal Territory (APIO21_hexagon) C++14
20 / 100
 95 ms 197448 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "hexagon.h"

const ll MOD = 1e9 + 7;

ll binpow(ll a, ll b) {
	if (b == 0) return 1;
	if (b & 1) return a*binpow(a, b-1) % MOD;
	ll ret = binpow(a, b/2);
	return ret*ret % MOD;
}
ll inv(ll x) {
	return binpow(x, MOD-2);
}
ll sum(ll n) {
	return n*(n+1) % MOD * inv(2) % MOD;
}
ll sumsq(ll n) {
	return n * (2*n+1) % MOD * (n+1) % MOD * inv(6) % MOD;
}

VPI harevan(int i, int j) {
	VPI ret;
	if (j & 1) {
		ret.pb({i-1, j});
		ret.pb({i-1, j+1});
		ret.pb({i, j+1});
		ret.pb({i+1, j});
		ret.pb({i, j-1});
		ret.pb({i-1, j-1});
	} else {
		ret.pb({i-1, j});
		ret.pb({i, j+1});
		ret.pb({i+1, j+1});
		ret.pb({i+1, j});
		ret.pb({i+1, j-1});
		ret.pb({i, j-1});
	}
	return ret;
}

int table[5000][5000];
int dist[5000][5000];

void dfs(int i, int j) {
	table[i][j] = 3;
	for (auto[vi, vj] : harevan(i, j)) if (table[vi][vj] == 2) {
		dfs(vi, vj);
	}
}

int draw_territory(int n, int A, int B, VI D, VI L) {
	if (n == 3) {
		ll x = L[0]+1;
		ll mas1 = sum(x) * A % MOD;
		ll mas2 = (sumsq(x) + MOD-sum(x))%MOD * B % MOD;
		return (mas1 + mas2) % MOD;
	}

	int ui = 2500, uj = 2500;
	rep(i, n) {
		int dir = D[i]-1;
		rep(j, L[i]) {
			auto[vi, vj] = harevan(ui, uj)[dir];
			table[ui][uj] = 1;
			ui = vi;
			uj = vj;
		}
	}

	int lmi, lmj = 1e9;
	replr(i, 1, 4998) replr(j, 1, 4998) if (table[i][j] == 1) {
		for (auto[vi, vj] : harevan(i, j)) {
			if (table[vi][vj] == 1) continue;
			if (vj < lmj) {
				lmi = vi;
				lmj = vj;
			}
			table[vi][vj] = 2;
		}
	}
	dfs(lmi, lmj);
	replr(i, 1, 4998) replr(j, 1, 4998) if (table[i][j] < 3) table[i][j] = 0;
	replr(i, 0, 4999) replr(j, 0, 4999) dist[i][j] = 2e9;
	queue<PII> q;
	q.push({2500, 2500});
	dist[2500][2500] = 0;
	VI ans{0};
	while (q.size()) {
		auto[ui, uj] = q.front();
		q.pop();
		for (auto[vi, vj] : harevan(ui, uj)) if (table[vi][vj] == 0 && dist[vi][vj] == 2e9) {
			dist[vi][vj] = dist[ui][uj]+1;

			ans.pb(dist[vi][vj]);

			q.push({vi, vj});
		}
	}

	/* for (int x : ans) cout << x << " "; cout << endl; */
	/* replr(i, 2500-6, 2500+6) { */
	/* 	replr(j, 2500-2, 2500+10) cout << table[i][j] << " "; */
	/* 	cout << endl; */
	/* } */

	ll ret = 0;
	for (int x : ans) {
		ll cur = (A + 1ll * x * B) % MOD;
		ret += cur;
		ret %= MOD;
	}
	return ret;
}

Compilation message

hexagon.cpp: In function 'void dfs(int, int)':
hexagon.cpp:77:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |  for (auto[vi, vj] : harevan(i, j)) if (table[vi][vj] == 2) {
      |           ^
hexagon.cpp: In function 'int draw_territory(int, int, int, VI, VI)':
hexagon.cpp:94:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   94 |    auto[vi, vj] = harevan(ui, uj)[dir];
      |        ^
hexagon.cpp:103:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |   for (auto[vi, vj] : harevan(i, j)) {
      |            ^
hexagon.cpp:120:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |   auto[ui, uj] = q.front();
      |       ^
hexagon.cpp:122:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  122 |   for (auto[vi, vj] : harevan(ui, uj)) if (table[vi][vj] == 0 && dist[vi][vj] == 2e9) {
      |            ^
hexagon.cpp:112:5: warning: 'lmi' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |  dfs(lmi, lmj);
      |  ~~~^~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 440 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 195920 KB Output is correct
2 Correct 80 ms 196492 KB Output is correct
3 Correct 74 ms 196232 KB Output is correct
4 Correct 75 ms 196120 KB Output is correct
5 Correct 70 ms 196180 KB Output is correct
6 Correct 73 ms 196312 KB Output is correct
7 Correct 77 ms 196176 KB Output is correct
8 Correct 73 ms 196184 KB Output is correct
9 Correct 73 ms 196184 KB Output is correct
10 Correct 72 ms 196180 KB Output is correct
11 Correct 75 ms 196176 KB Output is correct
12 Correct 84 ms 197448 KB Output is correct
13 Correct 83 ms 196880 KB Output is correct
14 Correct 95 ms 197392 KB Output is correct
15 Correct 71 ms 196180 KB Output is correct
16 Correct 78 ms 195952 KB Output is correct
17 Correct 72 ms 196048 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 100576 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 448 KB Output is correct
3 Runtime error 48 ms 100516 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 195936 KB Output is correct
2 Correct 75 ms 196580 KB Output is correct
3 Correct 73 ms 196236 KB Output is correct
4 Correct 73 ms 196176 KB Output is correct
5 Correct 78 ms 196720 KB Output is correct
6 Correct 72 ms 196104 KB Output is correct
7 Correct 73 ms 196288 KB Output is correct
8 Correct 72 ms 196012 KB Output is correct
9 Correct 73 ms 196176 KB Output is correct
10 Correct 79 ms 195988 KB Output is correct
11 Correct 73 ms 196176 KB Output is correct
12 Correct 83 ms 197392 KB Output is correct
13 Correct 84 ms 196956 KB Output is correct
14 Correct 89 ms 197388 KB Output is correct
15 Correct 77 ms 196200 KB Output is correct
16 Correct 74 ms 195924 KB Output is correct
17 Correct 75 ms 195924 KB Output is correct
18 Runtime error 48 ms 100436 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Runtime error 48 ms 100636 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 195984 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 77 ms 196544 KB Output is correct
7 Correct 73 ms 196224 KB Output is correct
8 Correct 71 ms 196176 KB Output is correct
9 Correct 71 ms 196176 KB Output is correct
10 Correct 72 ms 196176 KB Output is correct
11 Correct 78 ms 196356 KB Output is correct
12 Correct 72 ms 196180 KB Output is correct
13 Correct 77 ms 196024 KB Output is correct
14 Correct 73 ms 196176 KB Output is correct
15 Correct 74 ms 196216 KB Output is correct
16 Correct 90 ms 197332 KB Output is correct
17 Correct 84 ms 196880 KB Output is correct
18 Correct 86 ms 197288 KB Output is correct
19 Correct 76 ms 195968 KB Output is correct
20 Correct 83 ms 195992 KB Output is correct
21 Correct 73 ms 195924 KB Output is correct
22 Runtime error 47 ms 100436 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -