oj.uz

Submission #568683

# Submission time Handle Problem Language Result Execution time Memory
568683 2022-05-26T04:29:18 Z amunduzbaev Hexagonal Territory (APIO21_hexagon) C++17
32 / 100
 1598 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 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 = 2e5 + 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, tt; // 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]) tt.push_back(c);
				else tt.push_back(last);
			} 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, x[1] += _Y; 
		//~ cnt[x[0] + x[1]].push_back(x[1]);
	} 
	for(auto x : tt){
		x[0] += _X, x[1] += _Y;
		cnt[x[1]].push_back(x[0]);
	}
	
	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();
		j = cnt[y].size() - j;
		//~ for(auto x : cnt[y]) cout<<x<<" ";
		//~ cout<<"\n";
		//~ cout<<x<<" "<<y<<" "<<j<<"\n";
		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 = (int)t.size(), 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);
	}
	
	//~ cout<<subtask_4::solve(n, A, B, d, l)<<"\n";
	
	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++;
	} 
	
	//~ for(int i=1;i<=15;i++){
		//~ for(int j=1;j<=15;j++){
			//~ cout<<is[i][j]<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
	
	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);
			}
		}
	}
	
	//~ for(int i=1;i<=15;i++){
		//~ for(int j=1;j<=15;j++){
			//~ cout<<(!used[i][j])<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
	
	int res = 0; //, cc = 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;
			//~ cc = cc + A;
		}
	}
	
	//~ cout<<cc<<"\n";
	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 3 ms 4948 KB Output is correct
2 Correct 3 ms 4908 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct

Subtask #2
6.0 / 6.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 36468 KB Output is correct
2 Correct 128 ms 36432 KB Output is correct
3 Correct 161 ms 36452 KB Output is correct
4 Correct 124 ms 36456 KB Output is correct
5 Correct 117 ms 36468 KB Output is correct
6 Correct 145 ms 36464 KB Output is correct
7 Correct 122 ms 36432 KB Output is correct
8 Correct 165 ms 36492 KB Output is correct
9 Correct 126 ms 36476 KB Output is correct
10 Correct 122 ms 36556 KB Output is correct
11 Correct 121 ms 36548 KB Output is correct
12 Correct 121 ms 36532 KB Output is correct
13 Correct 122 ms 36436 KB Output is correct
14 Correct 131 ms 36424 KB Output is correct
15 Correct 120 ms 36500 KB Output is correct
16 Correct 116 ms 36436 KB Output is correct
17 Correct 123 ms 36464 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 10600 KB Output is correct
2 Correct 22 ms 7236 KB Output is correct
3 Correct 26 ms 7944 KB Output is correct
4 Correct 19 ms 6900 KB Output is correct
5 Correct 28 ms 8120 KB Output is correct
6 Correct 38 ms 8572 KB Output is correct
7 Correct 22 ms 7496 KB Output is correct
8 Correct 32 ms 8684 KB Output is correct
9 Correct 33 ms 8588 KB Output is correct
10 Correct 35 ms 8656 KB Output is correct
11 Correct 41 ms 9932 KB Output is correct
12 Correct 37 ms 10160 KB Output is correct
13 Correct 33 ms 9588 KB Output is correct
14 Correct 53 ms 10692 KB Output is correct
15 Correct 37 ms 9004 KB Output is correct
16 Correct 29 ms 7112 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5012 KB Output is correct
19 Correct 3 ms 5008 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 52 ms 10692 KB Output is correct
4 Correct 22 ms 7236 KB Output is correct
5 Correct 32 ms 8000 KB Output is correct
6 Correct 24 ms 6992 KB Output is correct
7 Correct 35 ms 8128 KB Output is correct
8 Correct 35 ms 8508 KB Output is correct
9 Correct 22 ms 7440 KB Output is correct
10 Correct 33 ms 8684 KB Output is correct
11 Correct 40 ms 8716 KB Output is correct
12 Correct 31 ms 8684 KB Output is correct
13 Correct 34 ms 9916 KB Output is correct
14 Correct 38 ms 10032 KB Output is correct
15 Correct 32 ms 9664 KB Output is correct
16 Correct 49 ms 10692 KB Output is correct
17 Correct 37 ms 9032 KB Output is correct
18 Correct 31 ms 7112 KB Output is correct
19 Runtime error 1598 ms 1048576 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 36532 KB Output is correct
2 Correct 120 ms 36380 KB Output is correct
3 Correct 127 ms 36456 KB Output is correct
4 Correct 125 ms 36388 KB Output is correct
5 Correct 124 ms 36484 KB Output is correct
6 Correct 120 ms 36396 KB Output is correct
7 Correct 134 ms 36484 KB Output is correct
8 Correct 149 ms 36404 KB Output is correct
9 Correct 118 ms 36440 KB Output is correct
10 Correct 139 ms 36404 KB Output is correct
11 Correct 157 ms 36532 KB Output is correct
12 Correct 147 ms 36488 KB Output is correct
13 Correct 123 ms 36496 KB Output is correct
14 Correct 150 ms 36396 KB Output is correct
15 Correct 122 ms 36404 KB Output is correct
16 Correct 134 ms 36448 KB Output is correct
17 Correct 117 ms 36400 KB Output is correct
18 Correct 40 ms 10600 KB Output is correct
19 Correct 23 ms 7360 KB Output is correct
20 Correct 26 ms 7904 KB Output is correct
21 Correct 21 ms 6964 KB Output is correct
22 Correct 30 ms 8128 KB Output is correct
23 Correct 34 ms 8560 KB Output is correct
24 Correct 21 ms 7484 KB Output is correct
25 Correct 31 ms 8684 KB Output is correct
26 Correct 34 ms 8708 KB Output is correct
27 Correct 31 ms 8708 KB Output is correct
28 Correct 35 ms 9936 KB Output is correct
29 Correct 37 ms 10136 KB Output is correct
30 Correct 34 ms 9708 KB Output is correct
31 Correct 53 ms 10652 KB Output is correct
32 Correct 36 ms 9076 KB Output is correct
33 Correct 29 ms 7180 KB Output is correct
34 Runtime error 8 ms 9956 KB Execution killed with signal 6
35 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Runtime error 8 ms 9896 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 135 ms 36460 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 131 ms 36500 KB Output is correct
7 Correct 128 ms 36388 KB Output is correct
8 Correct 139 ms 36484 KB Output is correct
9 Correct 120 ms 36392 KB Output is correct
10 Correct 120 ms 36436 KB Output is correct
11 Correct 120 ms 36448 KB Output is correct
12 Correct 136 ms 36384 KB Output is correct
13 Correct 127 ms 36428 KB Output is correct
14 Correct 140 ms 36440 KB Output is correct
15 Correct 118 ms 36416 KB Output is correct
16 Correct 126 ms 36604 KB Output is correct
17 Correct 137 ms 36472 KB Output is correct
18 Correct 132 ms 36500 KB Output is correct
19 Correct 128 ms 36504 KB Output is correct
20 Correct 137 ms 36428 KB Output is correct
21 Correct 118 ms 36496 KB Output is correct
22 Correct 42 ms 10612 KB Output is correct
23 Correct 23 ms 7236 KB Output is correct
24 Correct 31 ms 8004 KB Output is correct
25 Correct 20 ms 6900 KB Output is correct
26 Correct 33 ms 8072 KB Output is correct
27 Correct 34 ms 8508 KB Output is correct
28 Correct 22 ms 7496 KB Output is correct
29 Correct 29 ms 8684 KB Output is correct
30 Correct 32 ms 8588 KB Output is correct
31 Correct 31 ms 8668 KB Output is correct
32 Correct 34 ms 9864 KB Output is correct
33 Correct 39 ms 10016 KB Output is correct
34 Correct 34 ms 9580 KB Output is correct
35 Correct 56 ms 10680 KB Output is correct
36 Correct 39 ms 9076 KB Output is correct
37 Correct 27 ms 7112 KB Output is correct
38 Runtime error 1506 ms 1048576 KB Execution killed with signal 9
39 Halted 0 ms 0 KB -