oj.uz

Submission #568675

# Submission time Handle Problem Language Result Execution time Memory
568675 2022-05-26T03:36:27 Z amunduzbaev Hexagonal Territory (APIO21_hexagon) C++17
20 / 100
 1294 ms 1048576 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){
		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 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 4 ms 9684 KB Output is correct
2 Correct 6 ms 9708 KB Output is correct
3 Correct 5 ms 9708 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9712 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9688 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 41072 KB Output is correct
2 Correct 121 ms 41164 KB Output is correct
3 Correct 129 ms 41200 KB Output is correct
4 Correct 121 ms 41132 KB Output is correct
5 Correct 128 ms 41188 KB Output is correct
6 Correct 122 ms 41124 KB Output is correct
7 Correct 124 ms 41132 KB Output is correct
8 Correct 123 ms 41292 KB Output is correct
9 Correct 141 ms 41108 KB Output is correct
10 Correct 121 ms 41192 KB Output is correct
11 Correct 124 ms 41116 KB Output is correct
12 Correct 126 ms 41220 KB Output is correct
13 Correct 119 ms 41164 KB Output is correct
14 Correct 130 ms 41092 KB Output is correct
15 Correct 120 ms 41200 KB Output is correct
16 Correct 122 ms 41192 KB Output is correct
17 Correct 125 ms 41164 KB Output is correct
18 Correct 5 ms 9704 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 52 ms 14648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Incorrect 44 ms 14632 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 41184 KB Output is correct
2 Correct 121 ms 41104 KB Output is correct
3 Correct 130 ms 41160 KB Output is correct
4 Correct 120 ms 41156 KB Output is correct
5 Correct 126 ms 41164 KB Output is correct
6 Correct 121 ms 41108 KB Output is correct
7 Correct 123 ms 41092 KB Output is correct
8 Correct 123 ms 41116 KB Output is correct
9 Correct 121 ms 41084 KB Output is correct
10 Correct 123 ms 41164 KB Output is correct
11 Correct 125 ms 41188 KB Output is correct
12 Correct 123 ms 41376 KB Output is correct
13 Correct 121 ms 41084 KB Output is correct
14 Correct 123 ms 41084 KB Output is correct
15 Correct 122 ms 41124 KB Output is correct
16 Correct 120 ms 41120 KB Output is correct
17 Correct 123 ms 41156 KB Output is correct
18 Incorrect 41 ms 14648 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9600 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 Runtime error 1294 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 41148 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 9812 KB Output is correct
6 Correct 123 ms 41192 KB Output is correct
7 Correct 123 ms 41200 KB Output is correct
8 Correct 149 ms 41132 KB Output is correct
9 Correct 129 ms 41164 KB Output is correct
10 Correct 131 ms 41152 KB Output is correct
11 Correct 121 ms 41164 KB Output is correct
12 Correct 121 ms 41212 KB Output is correct
13 Correct 123 ms 41160 KB Output is correct
14 Correct 124 ms 41084 KB Output is correct
15 Correct 139 ms 41112 KB Output is correct
16 Correct 124 ms 41164 KB Output is correct
17 Correct 131 ms 41204 KB Output is correct
18 Correct 122 ms 41172 KB Output is correct
19 Correct 123 ms 41092 KB Output is correct
20 Correct 121 ms 41084 KB Output is correct
21 Correct 126 ms 41160 KB Output is correct
22 Incorrect 41 ms 14652 KB Output isn't correct
23 Halted 0 ms 0 KB -