oj.uz

Submission #528116

# Submission time Handle Problem Language Result Execution time Memory
528116 2022-02-19T10:18:08 Z Bilegt Hexagonal Territory (APIO21_hexagon) C++14
47 / 100
 1088 ms 270240 KB 
    #include "hexagon.h"
    #include <vector>
     
    using namespace std;
     
    typedef vector<int> vi;
     
    const int MD = 1000000007, V2 = 500000004, V6 = 166666668, INF = 0x3f3f3f3f, X = 2000;
     
    int max(int a, int b) { return a > b ? a : b; }
     
    int dx[] = { 1, 1, 0, -1, -1, 0 };
    int dy[] = { 0, 1, 1, 0, -1, -1 };
     
    int choose2(int n) {
    	return (long long) n * (n - 1) % MD * V2 % MD;
    }
     
    int choose3(int n) {
    	return (long long) n * (n - 1) % MD * (n - 2) % MD * V6 % MD;
    }
     
    char grid[X][X + 1]; int dd[X][X], qu[X * X], head, cnt;
     
    void dfs(int x, int y, char c) {
    	int h;
     
    	if (x < 0 || x >= X || y < 0 || y >= X || grid[x][y])
    		return;
    	grid[x][y] = c;
    	for (h = 0; h < 6; h++)
    		dfs(x + dx[h], y + dy[h], c);
    }
     
    long long cross(int x1, int y1, int x2, int y2) {
    	return (long long) x1 * y2 - (long long) x2 * y1;
    }
     
    int draw_territory(int n, int a, int b, vi hh, vi ll) {
    	int h, i, l, x, y, x_, y_, ans1, ans2;
    	long long area2, boundary, internal;
     
    	if (n == 3)
    		ans1 = choose2(ll[0] + 2), ans2 = choose3(ll[0] + 2) * 2 % MD;
    	else if (b == 0) {
    		x = 0, y = 0, area2 = 0, boundary = 0;
    		for (i = 0; i < n; i++) {
    			h = hh[i] - 1;
    			area2 += cross(x, y, x + dx[h] * ll[i], y + dy[h] * ll[i]);
    			boundary += ll[i];
    			x += dx[h] * ll[i], y += dy[h] * ll[i];
    		}
    		if (area2 < 0)
    			area2 = -area2;
    		internal = (area2 - boundary) / 2 + 1;
    		ans1 = (boundary + internal) % MD, ans2 = 0;
    	} else {
    		x = 1, y = 1;
    		for (i = 0; i < n; i++) {
    			h = hh[i] - 1;
    			for (l = 0; l < ll[i]; l++)
    				x = max(x + dx[h], 1), y = max(y + dy[h], 1);
    		}
    		x_ = x, y_ = y;
    		for (i = 0; i < n; i++) {
    			h = hh[i] - 1;
    			for (l = 0; l < ll[i]; l++)
    				grid[x += dx[h]][y += dy[h]] = 'X';
    		}
    		dfs(0, 0, ' ');
    		for (x = 0; x < X; x++)
    			for (y = 0; y < X; y++)
    				dfs(x, y, 'O');
    		ans1 = 0;
    		for (x = 0; x < X; x++)
    			for (y = 0; y < X; y++) {
    				dd[x][y] = INF;
    				if (grid[x][y] != ' ')
    					ans1++;
    			}
    		dd[x_][y_] = 0, qu[head + cnt++] = x_ * X + y_;
    		ans2 = 0;
    		while (cnt) {
    			int xy, d;
     
    			xy = qu[cnt--, head++], x = xy / X, y = xy % X, d = dd[x][y] + 1;
    			ans2 = (ans2 + dd[x][y]) % MD;
    			for (h = 0; h < 6; h++) {
    				int x_ = x + dx[h], y_ = y + dy[h];
     
    				if (x_ >= 0 && x_ < X && y_ >= 0 && y_ < X && grid[x_][y_] != ' ' && dd[x_][y_] > d)
    					dd[x_][y_] = d, qu[head + cnt++] = x_ * X + y_;
    			}
    		}
    	}
    	return ((long long) ans1 * a + (long long) ans2 * b) % MD;
    }

Subtask #1
3.0 / 3.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 270184 KB Output is correct
2 Correct 243 ms 264936 KB Output is correct
3 Correct 228 ms 267928 KB Output is correct
4 Correct 240 ms 268460 KB Output is correct
5 Correct 266 ms 266124 KB Output is correct
6 Correct 227 ms 268876 KB Output is correct
7 Correct 255 ms 267976 KB Output is correct
8 Correct 232 ms 269592 KB Output is correct
9 Correct 231 ms 270096 KB Output is correct
10 Correct 272 ms 269852 KB Output is correct
11 Correct 234 ms 269600 KB Output is correct
12 Correct 241 ms 258632 KB Output is correct
13 Correct 227 ms 258764 KB Output is correct
14 Correct 283 ms 258332 KB Output is correct
15 Correct 249 ms 270076 KB Output is correct
16 Correct 283 ms 270044 KB Output is correct
17 Correct 241 ms 269972 KB Output is correct
18 Correct 1 ms 208 KB Output is correct
19 Correct 1 ms 208 KB Output is correct
20 Correct 0 ms 208 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 436 KB Output is correct
7 Correct 4 ms 848 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 10 ms 1180 KB Output is correct
12 Correct 7 ms 1200 KB Output is correct
13 Correct 9 ms 1104 KB Output is correct
14 Correct 8 ms 1288 KB Output is correct
15 Correct 1 ms 296 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 0 ms 296 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 1 ms 232 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 292 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 2 ms 424 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 464 KB Output is correct
9 Correct 4 ms 932 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 292 KB Output is correct
12 Correct 0 ms 296 KB Output is correct
13 Correct 7 ms 1200 KB Output is correct
14 Correct 7 ms 1280 KB Output is correct
15 Correct 7 ms 1104 KB Output is correct
16 Correct 7 ms 1308 KB Output is correct
17 Correct 1 ms 208 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 0 ms 216 KB Output is correct
20 Correct 12 ms 2060 KB Output is correct
21 Correct 2 ms 464 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 14 ms 2660 KB Output is correct
24 Correct 27 ms 4040 KB Output is correct
25 Correct 23 ms 4296 KB Output is correct
26 Correct 11 ms 2300 KB Output is correct
27 Correct 9 ms 1744 KB Output is correct
28 Correct 5 ms 1232 KB Output is correct
29 Correct 27 ms 4648 KB Output is correct
30 Correct 28 ms 4788 KB Output is correct
31 Correct 31 ms 4652 KB Output is correct
32 Correct 26 ms 4400 KB Output is correct
33 Correct 12 ms 2168 KB Output is correct
34 Correct 7 ms 1176 KB Output is correct
35 Correct 1 ms 208 KB Output is correct
36 Correct 0 ms 208 KB Output is correct
37 Correct 1 ms 208 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 270188 KB Output is correct
2 Correct 249 ms 264936 KB Output is correct
3 Correct 245 ms 267944 KB Output is correct
4 Correct 242 ms 268460 KB Output is correct
5 Correct 236 ms 266092 KB Output is correct
6 Correct 226 ms 268816 KB Output is correct
7 Correct 263 ms 268076 KB Output is correct
8 Correct 235 ms 269628 KB Output is correct
9 Correct 227 ms 270124 KB Output is correct
10 Correct 246 ms 269872 KB Output is correct
11 Correct 242 ms 269640 KB Output is correct
12 Correct 246 ms 258696 KB Output is correct
13 Correct 262 ms 258728 KB Output is correct
14 Correct 239 ms 258400 KB Output is correct
15 Correct 259 ms 270024 KB Output is correct
16 Correct 236 ms 270024 KB Output is correct
17 Correct 239 ms 269992 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 2 ms 336 KB Output is correct
20 Correct 1 ms 208 KB Output is correct
21 Correct 1 ms 208 KB Output is correct
22 Correct 2 ms 336 KB Output is correct
23 Correct 2 ms 436 KB Output is correct
24 Correct 5 ms 848 KB Output is correct
25 Correct 0 ms 208 KB Output is correct
26 Correct 1 ms 296 KB Output is correct
27 Correct 0 ms 208 KB Output is correct
28 Correct 6 ms 1244 KB Output is correct
29 Correct 7 ms 1248 KB Output is correct
30 Correct 11 ms 1104 KB Output is correct
31 Correct 7 ms 1296 KB Output is correct
32 Correct 1 ms 208 KB Output is correct
33 Correct 1 ms 292 KB Output is correct
34 Runtime error 2 ms 340 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Runtime error 1088 ms 268 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 248 ms 270240 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 242 ms 264932 KB Output is correct
7 Correct 235 ms 267936 KB Output is correct
8 Correct 234 ms 268492 KB Output is correct
9 Correct 252 ms 266096 KB Output is correct
10 Correct 240 ms 268884 KB Output is correct
11 Correct 239 ms 267956 KB Output is correct
12 Correct 254 ms 269616 KB Output is correct
13 Correct 245 ms 270092 KB Output is correct
14 Correct 232 ms 269888 KB Output is correct
15 Correct 247 ms 269696 KB Output is correct
16 Correct 222 ms 258588 KB Output is correct
17 Correct 276 ms 258664 KB Output is correct
18 Correct 232 ms 258332 KB Output is correct
19 Correct 227 ms 270024 KB Output is correct
20 Correct 229 ms 270132 KB Output is correct
21 Correct 267 ms 270044 KB Output is correct
22 Correct 0 ms 208 KB Output is correct
23 Correct 2 ms 436 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 1 ms 208 KB Output is correct
26 Correct 1 ms 356 KB Output is correct
27 Correct 1 ms 464 KB Output is correct
28 Correct 4 ms 848 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 0 ms 308 KB Output is correct
31 Correct 0 ms 304 KB Output is correct
32 Correct 7 ms 1240 KB Output is correct
33 Correct 7 ms 1224 KB Output is correct
34 Correct 6 ms 1208 KB Output is correct
35 Correct 8 ms 1232 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 0 ms 208 KB Output is correct
38 Correct 0 ms 208 KB Output is correct
39 Correct 11 ms 1992 KB Output is correct
40 Correct 2 ms 468 KB Output is correct
41 Correct 1 ms 308 KB Output is correct
42 Correct 15 ms 2748 KB Output is correct
43 Correct 24 ms 4060 KB Output is correct
44 Correct 24 ms 4404 KB Output is correct
45 Correct 14 ms 2256 KB Output is correct
46 Correct 8 ms 1748 KB Output is correct
47 Correct 6 ms 1204 KB Output is correct
48 Correct 26 ms 4716 KB Output is correct
49 Correct 27 ms 4660 KB Output is correct
50 Correct 26 ms 4656 KB Output is correct
51 Correct 27 ms 4328 KB Output is correct
52 Correct 18 ms 2164 KB Output is correct
53 Correct 7 ms 1192 KB Output is correct
54 Runtime error 1 ms 336 KB Execution killed with signal 11
55 Halted 0 ms 0 KB -