oj.uz

Submission #979798

# Submission time Handle Problem Language Result Execution time Memory
979798 2024-05-11T11:32:03 Z c2zi6 Hexagonal Territory (APIO21_hexagon) C++14
20 / 100
 121 ms 197476 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;

namespace TEST2 {
	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;
	}
	int solve(int n, int A, int B, VI D, VI L) {
		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;
	}
}

namespace TEST3 {
	int table[5000][5000];
	int dist[5000][5000];
	VPI harevan(int i, int j) {
		VPI ret;
		ret.pb({i-1, j});
		ret.pb({i, j+1});
			ret.pb({i+1, j+1});
		ret.pb({i+1, j});
		ret.pb({i, j-1});
			ret.pb({i-1, j-1});
		return ret;
	}
	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 solve(int n, int A, int B, VI D, VI L) {
		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});
			}
		}
		ll ret = 0;
		for (int x : ans) {
			ll cur = (A + 1ll * x * B) % MOD;
			ret += cur;
			ret %= MOD;
		}
		return ret;
	}
}


int draw_territory(int n, int A, int B, VI D, VI L) {
	if (n == 3) return TEST2::solve(n, A, B, D, L);
	return TEST3::solve(n, A, B, D, L);
}

Compilation message

hexagon.cpp: In function 'void TEST3::dfs(int, int)':
hexagon.cpp:75:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |   for (auto[vi, vj] : harevan(i, j)) if (table[vi][vj] == 2) {
      |            ^
hexagon.cpp: In function 'int TEST3::solve(int, int, int, VI, VI)':
hexagon.cpp:84:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |     auto[vi, vj] = harevan(ui, uj)[dir];
      |         ^
hexagon.cpp:92:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |    for (auto[vi, vj] : harevan(i, j)) {
      |             ^
hexagon.cpp:109:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |    auto[ui, uj] = q.front();
      |        ^
hexagon.cpp:111:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  111 |    for (auto[vi, vj] : harevan(ui, uj)) if (table[vi][vj] == 0 && dist[vi][vj] == 2e9) {
      |             ^
hexagon.cpp:101:6: warning: 'lmi' may be used uninitialized in this function [-Wmaybe-uninitialized]
  101 |   dfs(lmi, lmj);
      |   ~~~^~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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 348 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 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 344 KB Output is correct
5 Correct 0 ms 344 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 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 196056 KB Output is correct
2 Correct 94 ms 196520 KB Output is correct
3 Correct 96 ms 196388 KB Output is correct
4 Correct 83 ms 196180 KB Output is correct
5 Correct 83 ms 196348 KB Output is correct
6 Correct 85 ms 196288 KB Output is correct
7 Correct 85 ms 196252 KB Output is correct
8 Correct 83 ms 196104 KB Output is correct
9 Correct 85 ms 196120 KB Output is correct
10 Correct 84 ms 196212 KB Output is correct
11 Correct 84 ms 196180 KB Output is correct
12 Correct 99 ms 197424 KB Output is correct
13 Correct 121 ms 196764 KB Output is correct
14 Correct 95 ms 197416 KB Output is correct
15 Correct 93 ms 196148 KB Output is correct
16 Correct 84 ms 195924 KB Output is correct
17 Correct 87 ms 196212 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 344 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 47 ms 100484 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 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Runtime error 47 ms 100444 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 86 ms 195924 KB Output is correct
2 Correct 95 ms 196548 KB Output is correct
3 Correct 84 ms 196200 KB Output is correct
4 Correct 87 ms 196104 KB Output is correct
5 Correct 83 ms 196208 KB Output is correct
6 Correct 83 ms 196304 KB Output is correct
7 Correct 90 ms 196176 KB Output is correct
8 Correct 83 ms 196180 KB Output is correct
9 Correct 84 ms 196176 KB Output is correct
10 Correct 83 ms 196144 KB Output is correct
11 Correct 87 ms 195968 KB Output is correct
12 Correct 100 ms 197448 KB Output is correct
13 Correct 94 ms 197216 KB Output is correct
14 Correct 96 ms 197476 KB Output is correct
15 Correct 82 ms 196116 KB Output is correct
16 Correct 84 ms 195916 KB Output is correct
17 Correct 92 ms 195872 KB Output is correct
18 Runtime error 47 ms 100564 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 348 KB Output is correct
2 Correct 1 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 Runtime error 48 ms 100552 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 84 ms 195900 KB Output is correct
2 Correct 1 ms 500 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 348 KB Output is correct
6 Correct 88 ms 196452 KB Output is correct
7 Correct 85 ms 196436 KB Output is correct
8 Correct 83 ms 196136 KB Output is correct
9 Correct 109 ms 196232 KB Output is correct
10 Correct 85 ms 196312 KB Output is correct
11 Correct 85 ms 196196 KB Output is correct
12 Correct 84 ms 196096 KB Output is correct
13 Correct 83 ms 196160 KB Output is correct
14 Correct 84 ms 196012 KB Output is correct
15 Correct 83 ms 196172 KB Output is correct
16 Correct 94 ms 197448 KB Output is correct
17 Correct 95 ms 196880 KB Output is correct
18 Correct 100 ms 197392 KB Output is correct
19 Correct 83 ms 196180 KB Output is correct
20 Correct 85 ms 195920 KB Output is correct
21 Correct 83 ms 195924 KB Output is correct
22 Runtime error 52 ms 100416 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -