oj.uz

Submission #568676

# Submission time Handle Problem Language Result Execution time Memory
568676 2022-05-26T03:37:09 Z amunduzbaev Hexagonal Territory (APIO21_hexagon) C++17
20 / 100
 161 ms 41320 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 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){
	int ch[6][3] = {
		{1, 1},
		{1, 0},
		{0, -1},
		{-1, -1},
		{-1, 0},
		{0, 1}
	};
	
	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;
	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[x + y].begin(), cnt[x + y].end(), y) - cnt[x + 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;
			int y = t[k - 1] + 1;
			if(check(x, y)){
				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);
	}
	
	//~ assert(false);
	int ch[6][3] = {
		{1, 1},
		{1, 0},
		{0, -1},
		{-1, -1},
		{-1, 0},
		{0, 1}
	};
	
	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 9660 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 9672 KB Output is correct
3 Correct 6 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 7 ms 9684 KB Output is correct
7 Correct 7 ms 9812 KB Output is correct
8 Correct 6 ms 9688 KB Output is correct
9 Correct 5 ms 9640 KB Output is correct
10 Correct 5 ms 9608 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9704 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 41236 KB Output is correct
2 Correct 132 ms 41080 KB Output is correct
3 Correct 125 ms 41128 KB Output is correct
4 Correct 119 ms 41084 KB Output is correct
5 Correct 129 ms 41320 KB Output is correct
6 Correct 126 ms 41124 KB Output is correct
7 Correct 127 ms 41192 KB Output is correct
8 Correct 130 ms 41184 KB Output is correct
9 Correct 128 ms 41200 KB Output is correct
10 Correct 125 ms 41108 KB Output is correct
11 Correct 123 ms 41168 KB Output is correct
12 Correct 131 ms 41176 KB Output is correct
13 Correct 133 ms 41180 KB Output is correct
14 Correct 138 ms 41148 KB Output is correct
15 Correct 122 ms 41156 KB Output is correct
16 Correct 121 ms 41292 KB Output is correct
17 Correct 123 ms 41084 KB Output is correct
18 Correct 6 ms 9696 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 5 ms 9684 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 14640 KB Output isn't correct
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 Incorrect 42 ms 14648 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 41080 KB Output is correct
2 Correct 124 ms 41184 KB Output is correct
3 Correct 136 ms 41196 KB Output is correct
4 Correct 132 ms 41164 KB Output is correct
5 Correct 122 ms 41116 KB Output is correct
6 Correct 119 ms 41092 KB Output is correct
7 Correct 121 ms 41168 KB Output is correct
8 Correct 128 ms 41248 KB Output is correct
9 Correct 135 ms 41196 KB Output is correct
10 Correct 121 ms 41160 KB Output is correct
11 Correct 122 ms 41144 KB Output is correct
12 Correct 126 ms 41172 KB Output is correct
13 Correct 128 ms 41164 KB Output is correct
14 Correct 132 ms 41220 KB Output is correct
15 Correct 161 ms 41164 KB Output is correct
16 Correct 134 ms 41164 KB Output is correct
17 Correct 134 ms 41212 KB Output is correct
18 Incorrect 43 ms 14664 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 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 9588 KB Output is correct
5 Runtime error 13 ms 19424 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 125 ms 41152 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9656 KB Output is correct
6 Correct 126 ms 41156 KB Output is correct
7 Correct 128 ms 41196 KB Output is correct
8 Correct 138 ms 41260 KB Output is correct
9 Correct 143 ms 41072 KB Output is correct
10 Correct 122 ms 41148 KB Output is correct
11 Correct 125 ms 41188 KB Output is correct
12 Correct 136 ms 41132 KB Output is correct
13 Correct 131 ms 41224 KB Output is correct
14 Correct 120 ms 41100 KB Output is correct
15 Correct 124 ms 41164 KB Output is correct
16 Correct 128 ms 41164 KB Output is correct
17 Correct 137 ms 41116 KB Output is correct
18 Correct 127 ms 41184 KB Output is correct
19 Correct 123 ms 41164 KB Output is correct
20 Correct 121 ms 41100 KB Output is correct
21 Correct 127 ms 41136 KB Output is correct
22 Incorrect 43 ms 14644 KB Output isn't correct
23 Halted 0 ms 0 KB -