oj.uz

Submission #568682

# Submission time Handle Problem Language Result Execution time Memory
568682 2022-05-26T04:06:23 Z amunduzbaev Hexagonal Territory (APIO21_hexagon) C++17
20 / 100
 146 ms 41312 KB 
#include "hexagon.h"

#ifndef EVAL
#include "grader.cpp"
#endif

#include "bits/stdc++.h"
using namespace std;
#define ar array
using ll = long long;
const int mod = 1e9 + 7;
const int N = 2e3 + 5;
int is[N][N], used[N][N];
int ch[6][3] = {
	{1, 1},
	{1, 0},
	{0, -1},
	{-1, -1},
	{-1, 0},
	{0, 1}
};

int bp(int a, int b){
	int r = 1;
	while(b){
		if(b & 1) r = r * 1ll * a % mod;
		b >>= 1, a = a * 1ll * a % mod;
	} return r;
}

namespace subtask_4{
const int N = 4e5 + 5;
vector<int> cnt[N];

int solve(int n, int A, int B, vector<int> d, vector<int> l){
	
	ar<int, 2> c {}; 
	vector<ar<int, 2>> p; // p.push_back(c);
	int _X = 0, _Y = 0;
	for(int i=0;i<n;i++){ --d[i];
		for(int k=0;k<l[i];k++){
			ar<int, 2> last = c;
			for(int t=0;t<2;t++) c[t] += ch[d[i]][t];
			if(c[1] != last[1]){
				if(c[1] > last[1]) cnt[c[1]].push_back(c[0]);
				else cnt[last[1]].push_back(last[0]);
			} p.push_back(c);
			_X = min(_X, c[0]);
			_Y = min(_Y, c[1]);
		}
	}
	
	_X = 1 - _X, _Y = 1 - _Y;
	for(auto& x : p){
		x[0] = x[0] + _X; 
		x[1] = x[1] + _Y; 
		//~ cnt[x[0] + x[1]].push_back(x[1]);
	} 
	
	for(int i=0;i<N;i++) sort(cnt[i].begin(), cnt[i].end());
	auto check = [&](int x, int y){
		int j = lower_bound(cnt[y].begin(), cnt[y].end(), x) - cnt[y].begin();
		return (j & 1);
	};
	
	sort(p.begin(), p.end());
	int res = 0;
	for(int i=0, j=0;i<(int)p.size(); i = j){
		vector<int> t;
		while(j < (int)p.size() && p[i][0] == p[j][0]){
			t.push_back(p[j][1]);
			j++;
		}
		int m = j - i, x = p[i][0];
		res = (res + m) % mod;
		for(int k=1;k<m;k++){
			if(t[k - 1] + 1 == t[k]) continue;
			if(check(x, t[k - 1] + 1)){
				res = (res + t[k] - t[k - 1] - 1);
			}
		}
	}
	
	res = res * 1ll * A % mod;
	return res;
}

};

int draw_territory(int n, int A, int B, vector<int> d, vector<int> l) {
	if(n == 3){
		int L = l[0];
		int res = (L + 1) * 1ll * (L + 2) / 2 % mod * A % mod;
		res = (res + L * 1ll * (L + 1) % mod * (2 * L + 1) % mod * bp(6, mod - 2) % mod * B % mod) % mod; 
		res = (res + L * 1ll * (L + 1) / 2 % mod * B % mod) % mod;
		return res;
	}
	
	ll sum = accumulate(l.begin(), l.end(), 0ll);
	if(sum > 2000){
		assert(B == 0);
		return subtask_4::solve(n, A, B, d, l);
	}
	
	ar<int, 2> c {}; 
	vector<ar<int, 2>> p; p.push_back(c);
	int _X = 0, _Y = 0;
	for(int i=0;i<n;i++){ --d[i];
		for(int k=0;k<l[i];k++){
			for(int t=0;t<2;t++) c[t] += ch[d[i]][t];
			p.push_back(c);
			_X = min(_X, c[0]);
			_Y = min(_Y, c[1]);
		}
	}
	
	_X = 1 - _X, _Y = 1 - _Y;
	int last = 1;
	for(auto& x : p){
		x[0] = x[0] + _X; 
		x[1] = x[1] + _Y; 
		is[x[0]][x[1]] = last++;
	} 
	
	queue<int> q;
	for(int i=0;i<N;i++){
		used[0][i] = used[i][0] = used[N - 1][i] = used[i][N - 1] = 1;
		q.push(i);
		q.push(N * (N - 1) + i);
		if(i && i + 1 < N){
			q.push(i * N);
			q.push(i * N + N - 1);
		}
	}
	
	auto check = [&](int x, int y) { return (0 <= x && x < N && 0 <= y && y < N); };
	
	while(!q.empty()){
		int u = q.front(); q.pop();
		int x = u / N, y = u % N;
		for(int t=0;t<6;t++){
			int tx = x + ch[t][0], ty = y + ch[t][1];
			if(check(tx, ty) && !is[tx][ty] && !used[tx][ty]){
				used[tx][ty] = 1;
				q.push(tx * N + ty);
			}
		}
	}
	
	memset(is, 0, sizeof is);
	q.push(_X * N + _Y);
	is[_X][_Y] = 1;
	while(!q.empty()){
		int u = q.front(); q.pop();
		int x = u / N, y = u % N;
		for(int t=0;t<6;t++){
			int tx = x + ch[t][0], ty = y + ch[t][1];
			if(check(tx, ty) && !is[tx][ty] && !used[tx][ty]){
				is[tx][ty] = is[x][y] + 1;
				q.push(tx * N + ty);
			}
		}
	}
	
	int res = 0;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(!is[i][j]) continue;
			is[i][j]--;
			//~ D[is[i][j]]++;
			//~ cout<<is[i][j]<<" "<<i<<" "<<j<<"\n";
			res = (res + is[i][j] * 1ll * B + A) % mod;
		}
	}
	
	return res;
}

/*

17 2 3
1 1
2 2
3 2
4 1
5 1
4 1
3 1
2 2
1 3
6 2
2 3
3 1
4 6
5 3
6 3
6 2
1 1

*/

Subtask #1
3.0 / 3.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9604 KB Output is correct
9 Correct 5 ms 9656 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 41128 KB Output is correct
2 Correct 124 ms 41216 KB Output is correct
3 Correct 124 ms 41164 KB Output is correct
4 Correct 146 ms 41216 KB Output is correct
5 Correct 122 ms 41104 KB Output is correct
6 Correct 127 ms 41164 KB Output is correct
7 Correct 124 ms 41068 KB Output is correct
8 Correct 130 ms 41096 KB Output is correct
9 Correct 128 ms 41144 KB Output is correct
10 Correct 130 ms 41164 KB Output is correct
11 Correct 129 ms 41096 KB Output is correct
12 Correct 127 ms 41284 KB Output is correct
13 Correct 131 ms 41188 KB Output is correct
14 Correct 146 ms 41196 KB Output is correct
15 Correct 135 ms 41196 KB Output is correct
16 Correct 121 ms 41184 KB Output is correct
17 Correct 123 ms 41164 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 5 ms 9696 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 19452 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 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Runtime error 14 ms 19412 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 128 ms 41128 KB Output is correct
2 Correct 136 ms 41144 KB Output is correct
3 Correct 130 ms 41124 KB Output is correct
4 Correct 129 ms 41204 KB Output is correct
5 Correct 123 ms 41088 KB Output is correct
6 Correct 123 ms 41092 KB Output is correct
7 Correct 139 ms 41140 KB Output is correct
8 Correct 132 ms 41148 KB Output is correct
9 Correct 120 ms 41196 KB Output is correct
10 Correct 132 ms 41144 KB Output is correct
11 Correct 143 ms 41124 KB Output is correct
12 Correct 132 ms 41192 KB Output is correct
13 Correct 124 ms 41164 KB Output is correct
14 Correct 120 ms 41100 KB Output is correct
15 Correct 133 ms 41164 KB Output is correct
16 Correct 136 ms 41164 KB Output is correct
17 Correct 124 ms 41160 KB Output is correct
18 Runtime error 14 ms 19464 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 5 ms 9688 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9632 KB Output is correct
5 Runtime error 14 ms 19488 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 41128 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9664 KB Output is correct
4 Correct 5 ms 9620 KB Output is correct
5 Correct 7 ms 9684 KB Output is correct
6 Correct 132 ms 41196 KB Output is correct
7 Correct 140 ms 41308 KB Output is correct
8 Correct 122 ms 41164 KB Output is correct
9 Correct 124 ms 41108 KB Output is correct
10 Correct 122 ms 41304 KB Output is correct
11 Correct 127 ms 41160 KB Output is correct
12 Correct 127 ms 41116 KB Output is correct
13 Correct 145 ms 41128 KB Output is correct
14 Correct 141 ms 41156 KB Output is correct
15 Correct 133 ms 41312 KB Output is correct
16 Correct 125 ms 41096 KB Output is correct
17 Correct 124 ms 41104 KB Output is correct
18 Correct 125 ms 41124 KB Output is correct
19 Correct 142 ms 41112 KB Output is correct
20 Correct 131 ms 41176 KB Output is correct
21 Correct 134 ms 41092 KB Output is correct
22 Runtime error 14 ms 19420 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -