oj.uz

답안 #727890

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
727890 2023-04-21T14:15:53 Z SanguineChameleon 육각형 영역 (APIO21_hexagon) C++17
66 / 100
 2000 ms 98140 KB 
#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;

#ifdef KAMIRULEZ
	const bool local = true;
	const int subtask = 6;
#else
	const bool local = false;
	const int subtask = -1;
#endif

const long long mod = 1e9 + 7;
const long long one_half = (mod + 1) / 2;
const long long one_third = (mod + 1) / 3;
const int dx[7] = {0, 0, 1, 1, 0, -1, -1};
const int dy[7] = {0, 1, 1, 0, -1, -1, 0};

struct point {
	long long x, y;

	point() {};

	point(long long _x, long long _y): x(_x), y(_y) {};

	point operator*(long long d) {
		return point(x * d, y * d);
	}

	point operator+(point p2) {
		return point(x + p2.x, y + p2.y);
	}

	long long operator^(point p2) {
		return x * p2.y - y * p2.x;
	}
};

point dv[7] = {point(0, 0), point(0, 1), point(1, 1), point(1, 0), point(0, -1), point(-1, -1), point(-1, 0)};

ostream& operator<<(ostream &out, point p) {
	out << "(" << p.x << "," << p.y << ")";
	return out;
}

struct line {
	int type, dir, len;
	point p1, p2;
	int id;

	line() {};

	line(int _type, int _dir, point _p1, point _p2, int _id): type(_type), dir(_dir), p1(_p1), p2(_p2), id(_id) {
		len = p2.x - p1.x + 1;
	};

	long long calc() {
		long long Ly = p1.y;
		long long Ry = p1.y + (dir == 1 ? 0 : len - 1);
		if (type == 1) {
			Ly = 1 - Ly;
			Ry = 1 - Ry;
		}
		return (Ly + Ry) % mod * len % mod * one_half % mod;
	}

	long long eval_x(long long x) {
		if (dir == 1) {
			return p1.y;
		}
		else {
			return p1.y + (x - p1.x);
		}
	}

	void shorten(long long left_x, long long right_x) {
		long long v1 = eval_x(left_x);
		long long v2 = eval_x(right_x);
		p1 = point(left_x, v1);
		p2 = point(right_x, v2);
	}
};

ostream& operator<<(ostream &out, line L) {
	if (L.type == 1) {
		out << "(bottom,";
	}
	else {
		out << "(top,";
	}
	out << L.p1 << "," << L.p2 << ")";
	return out;
}

bool operator<(line L1, line L2) {
	int max_x = max(L1.p1.x, L2.p1.x);
	int v1 = L1.eval_x(max_x);
	int v2 = L2.eval_x(max_x);
	if (v1 != v2) {
		return v1 < v2;
	}
	else {
		return L1.type < L2.type;
	}
};

struct column {
	long long x, left_y, right_y, min_dist, left_min, right_min;

	column() {};

	column(long long _x, long long _left_y, long long _right_y): x(_x), left_y(_left_y), right_y(_right_y) {};

	column(long long _x, long long _left_y, long long _right_y, long long _min_dist, long long _left_min, long long _right_min): x(_x), left_y(_left_y), right_y(_right_y), min_dist(_min_dist), left_min(_left_min), right_min(_right_min) {};

	long long calc(long long A, long long B) {
		long long left_len = (left_min - left_y) % mod;
		long long mid_len = (right_min - left_min + 1) % mod;
		long long right_len = (right_y - right_min) % mod;
		long long A_sum = (right_y - left_y + 1) % mod;
		long long B_sum = (min_dist * mid_len % mod + (min_dist + 1 + min_dist + left_len) * left_len % mod * one_half % mod + (min_dist + 1 + min_dist + right_len) * right_len % mod * one_half % mod) % mod;
		return (A_sum * A + B_sum * B) % mod;
	}
};

ostream& operator<<(ostream &out, column Col) {
	out << "(" << Col.x << ",(" << Col.left_y << "," << Col.right_y << "),min=" << Col.min_dist << ",(" << Col.left_min << "," << Col.right_min << "))";
	return out;
}

struct comp {
	line bottom, top;
	int left_x, right_x, len;
	column left_col, right_col;
	long long sum;

	comp() {};

	comp(line _bottom, line _top, int _left_x, int _right_x): bottom(_bottom), top(_top), left_x(_left_x), right_x(_right_x) {
		bottom.shorten(left_x, right_x);
		top.shorten(left_x, right_x);
		len = right_x - left_x + 1;
	}

	long long calc() {
		long long Ly = top.p1.y - bottom.p1.y + 1;
		long long Ry = top.p2.y - bottom.p2.y + 1;
		return (Ly + Ry) % mod * len % mod * one_half % mod;
	}
};

ostream& operator<<(ostream &out, comp C) {
	out << "(" << C.bottom << "," << C.top << ",(" << C.left_x << "," << C.right_x << "))";
	return out;
}

column move_right_one(column Col1, column Col2) {
	if (Col2.left_y > Col1.right_min + 1) {
		Col2.min_dist = Col2.left_y - (Col1.right_min + 1) + (Col1.min_dist + 1);
		Col2.left_min = Col2.left_y;
		Col2.right_min = Col2.left_y;
		return Col2;
	}
	if (Col2.right_y < Col1.left_min) {
		Col2.min_dist = Col1.left_min - Col2.right_y + (Col1.min_dist + 1);
		Col2.left_min = Col2.right_y;
		Col2.right_min = Col2.right_y;
		return Col2;
	}
	Col2.min_dist = Col1.min_dist + 1;
	Col2.left_min = max(Col2.left_y, Col1.left_min);
	Col2.right_min = min(Col2.right_y, Col1.right_min + 1);
	return Col2;
}

column move_left_one(column Col1, column Col2) {
	if (Col2.left_y > Col1.right_min) {
		Col2.min_dist = Col2.left_y - Col1.right_min + (Col1.min_dist + 1);
		Col2.left_min = Col2.left_y;
		Col2.right_min = Col2.left_y;
		return Col2;
	}
	if (Col2.right_y < Col1.left_min - 1) {
		Col2.min_dist = (Col1.left_min - 1) - Col2.right_y + (Col1.min_dist + 1);
		Col2.left_min = Col2.right_y;
		Col2.right_min = Col2.right_y;
		return Col2;
	}
	Col2.min_dist = Col1.min_dist + 1;
	Col2.left_min = max(Col2.left_y, Col1.left_min - 1);
	Col2.right_min = min(Col2.right_y, Col1.right_min);
	return Col2;
}

pair<long long, column> move_right(column Col, line bottom, line top, long long left_x, long long right_x, long long A, long long B) {
	column cur = Col;
	long long res = cur.calc(A, B);
	for (int x = left_x + 1; x <= right_x; x++) {
		column nxt = move_right_one(cur, column(x, bottom.eval_x(x), top.eval_x(x)));
		res += nxt.calc(A, B);
		res %= mod;
		cur = nxt;
	}
	return make_pair(res, cur);
}

pair<long long, column> move_left(column Col, line bottom, line top, long long right_x, long long left_x, long long A, long long B) {
	column cur = Col;
	long long res = cur.calc(A, B);
	for (int x = right_x - 1; x >= left_x; x--) {
		column nxt = move_left_one(cur, column(x, bottom.eval_x(x), top.eval_x(x)));
		res += nxt.calc(A, B);
		res %= mod;
		cur = nxt;
	}
	return make_pair(res, cur);
}

vector<comp> comps;
vector<vector<int>> adj;

void dfs(int u, int par, long long A, long long B) {
	for (auto v: adj[u]) {
		if (v == par) {
			continue;
		}
		if (comps[u].right_x + 1 == comps[v].left_x) {
			comps[v].left_col = move_right_one(comps[u].right_col, column(comps[v].left_x, comps[v].bottom.p1.y, comps[v].top.p1.y));
			auto p_right = move_right(comps[v].left_col, comps[v].bottom, comps[v].top, comps[v].left_x, comps[v].right_x, A, B);
			comps[v].sum = p_right.first;
			comps[v].right_col = p_right.second;
		}
		else {
			comps[v].right_col = move_left_one(comps[u].left_col, column(comps[v].right_x, comps[v].bottom.p2.y, comps[v].top.p2.y));
			auto p_left = move_left(comps[v].right_col, comps[v].bottom, comps[v].top, comps[v].right_x, comps[v].left_x, A, B);
			comps[v].sum = p_left.first;
			comps[v].left_col = p_left.second;
		}
		dfs(v, u, A, B);
	}
}

int draw_territory(int N, int A, int B, vector<int> D, vector<int> L) {
	if (N == 3 && (!local || subtask == 1 || subtask == 2)) {
		int len = L[0] + 1;
		long long A_sum = 1LL * len * (len + 1) % mod * one_half % mod;
		long long B_sum = 1LL * len * (len - 1) % mod * one_half % mod + (len - 1) * len % mod * (len * 2 - 1) % mod * one_half % mod * one_third % mod;
		return (A_sum * A + B_sum * B) % mod;
	}
	long long L_sum = 0;
	for (int i = 0; i < N; i++) {
		L_sum += L[i];
	}
	if (L_sum <= 2000 && (!local || subtask == 3)) {
		vector<vector<bool>> border(4069, vector<bool>(4069, false));
		vector<vector<int>> dist(4069, vector<int>(4069, -1));
		int cx = 0;
		int cy = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < L[i]; j++) {
				cx += dx[D[i]];
				cy += dy[D[i]];
				border[cx + 2023][cy + 2023] = true;
			}
		}
		deque<pair<int, int>> q = {{0, 0}};
		dist[0][0] = -2;
		while (!q.empty()) {
			cx = q.front().first;
			cy = q.front().second;
			q.pop_front();
			for (int d = 1; d <= 6; d++) {
				int nx = cx + dx[d];
				int ny = cy + dy[d];
				if (0 <= nx && nx < 4069 && 0 <= ny && ny < 4069 && !border[nx][ny] && dist[nx][ny] == -1) {
					dist[nx][ny] = -2;
					q.push_back({nx, ny});
				}
			}
		}
		q.push_back({2023, 2023});
		dist[2023][2023] = 0;
		long long res = 0;
		while (!q.empty()) {
			cx = q.front().first;
			cy = q.front().second;
			res += 1LL * B * dist[cx][cy] + A;
			res %= mod;
			q.pop_front();
			for (int d = 1; d <= 6; d++) {
				int nx = cx + dx[d];
				int ny = cy + dy[d];
				if (0 <= nx && nx < 4069 && 0 <= ny && ny < 4069 && dist[nx][ny] == -1) {
					dist[nx][ny] = dist[cx][cy] + 1;
					q.push_back({nx, ny});
				}
			}
		}
		return res;
	}
	long long area = 0;
	point cur = point(0, 0);
	vector<point> poly(N);
	for (int i = 0; i < N; i++) {
		poly[i] = cur;
		cur = cur + (dv[D[i]] * L[i]);
	}
	for (int i = 0; i < N; i++) {
		area += poly[i] ^ poly[(i + 1) % N];
	}
	if (area < 0) {
		reverse(D.begin(), D.end());
		for (int i = 0; i < N; i++) {
			if (D[i] <= 3) {
				D[i] += 3;
			}
			else {
				D[i] -= 3;
			}
		}
		reverse(L.begin(), L.end());
		cur = point(0, 0);
		for (int i = 0; i < N; i++) {
			poly[i] = cur;
			cur = cur + (dv[D[i]] * L[i]);
		}
	}
	vector<line> lines;
	vector<int> prv_x;
	for (int i = 0; i < N; i++) {
		point prv = poly[(i + (N - 1)) % N];
		point cur = poly[i];
		point nxt1 = poly[(i + 1) % N];
		point nxt2 = poly[(i + 2) % N];
		if (cur.x < nxt1.x) {
			point p1 = cur;
			point p2 = nxt1;
			int dir = (cur.y == nxt1.y ? 1 : 2);
			if (prv.x < cur.x) {
				if (dir == 1) {
					p1 = p1 + point(1, 0);
				}
				else {
					p1 = p1 + point(1, 1);
				}
			}
			if (prv.x == cur.x && prv.y < cur.y) {
				if (dir == 1) {
					p1 = p1 + point(1, 0);
				}
				else {
					p1 = p1 + point(1, 1);
				}
			}
			if (nxt1.x == nxt2.x && nxt1.y > nxt2.y) {
				if (dir == 1) {
					p2 = p2 + point(-1, 0);
				}
				else {
					p2 = p2 + point(-1, -1);
				}
			}
			if (p1.x <= p2.x) {
				lines.emplace_back(1, dir, p1, p2, lines.size());
				prv_x.push_back(p1.x);
			}
		}
		if (cur.x > nxt1.x) {
			point p1 = nxt1;
			point p2 = cur;
			int dir = (cur.y == nxt1.y ? 1 : 2);
			if (prv.x > cur.x) {
				if (dir == 1) {
					p2 = p2 + point(-1, 0);
				}
				else {
					p2 = p2 + point(-1, -1);
				}
			}
			if (prv.x == cur.x && prv.y > cur.y) {
				if (dir == 1) {
					p2 = p2 + point(-1, 0);
				}
				else {
					p2 = p2 + point(-1, -1);
				}
			}
			if (nxt1.x == nxt2.x && nxt1.y < nxt2.y) {
				if (dir == 1) {
					p1 = p1 + point(1, 0);
				}
				else {
					p1 = p1 + point(1, 1);
				}
			}
			if (p1.x <= p2.x) {
				lines.emplace_back(2, dir, p1, p2, lines.size());
				prv_x.push_back(p1.x);
			}
		}
	}
	vector<pair<int, pair<int, int>>> events;
	for (int i = 0; i < (int)lines.size(); i++) {
		events.push_back(make_pair(lines[i].p1.x - 1, make_pair(2, i)));
		events.push_back(make_pair(lines[i].p1.x, make_pair(0, i)));
		events.push_back(make_pair(lines[i].p2.x, make_pair(1, i)));
	}
	sort(events.begin(), events.end());
	set<line, less<>> S;
	for (auto e: events) {
		int cur_x = e.first;
		int type = e.second.first;
		line L = lines[e.second.second];
		auto it = (type == 0 ? S.insert(L).first : S.lower_bound(L));
		if (type == 1) {
			if (it->type == 1 && next(it) != S.end()) {
				auto bottom = it;
				auto top = next(it);
				if (prv_x[bottom->id] <= cur_x && prv_x[top->id] <= cur_x) {
					comps.emplace_back(*bottom, *top, prv_x[bottom->id], cur_x);
					prv_x[bottom->id] = cur_x + 1;
					prv_x[top->id] = cur_x + 1;
				}
			}
			if (it->type == 2 && it != S.begin()) {
				auto bottom = prev(it);
				auto top = it;
				if (prv_x[bottom->id] <= cur_x && prv_x[top->id] <= cur_x) {
					comps.emplace_back(*bottom, *top, prv_x[bottom->id], cur_x);
					prv_x[bottom->id] = cur_x + 1;
					prv_x[top->id] = cur_x + 1;
				}
			}
			S.erase(it);
		}
		if (type == 2) {
			if (it != S.end() && it != S.begin()) {
				auto bottom = prev(it);
				auto top = it;
				if (bottom->type == 1 && top->type == 2) {
					if (prv_x[bottom->id] <= cur_x && prv_x[top->id] <= cur_x) {
						comps.emplace_back(*bottom, *top, prv_x[bottom->id], cur_x);
						prv_x[bottom->id] = cur_x + 1;
						prv_x[top->id] = cur_x + 1;
					}
				}
			}
		}
	}
	adj.resize(comps.size());
	events.clear();
	for (int i = 0; i < (int)comps.size(); i++) {
		events.push_back(make_pair(comps[i].right_x + 1, make_pair(comps[i].bottom.p2.y, i)));
		events.push_back(make_pair(comps[i].left_x, make_pair(comps[i].bottom.p1.y, -i - 1)));
	}
	sort(events.begin(), events.end());
	int lid = -1;
	int rid = -1;
	int edge_cnt = 0;
	for (auto e: events) {
		if (e.second.second >= 0) {
			lid = e.second.second;
		}
		else {
			rid = -e.second.second - 1;
		}
		if (lid >= 0 && rid >= 0 && comps[lid].right_x + 1 == comps[rid].left_x && max(comps[lid].bottom.p2.y, comps[rid].bottom.p1.y) <= min(comps[lid].top.p2.y + 1, comps[rid].top.p1.y)) {
			adj[lid].push_back(rid);
			adj[rid].push_back(lid);
			edge_cnt++;
		}
	}
	if (B == 0 && (!local || subtask == 4 || subtask == 5)) {
		long long res = 0;
		for (auto C: comps) {
			res += C.calc();
			res %= mod;
		}
		if (res < 0) {
			res += mod;
		}
		res = res * A % mod;
		return res;
	}
	int root = -1;
	for (int i = 0; i < (int)comps.size(); i++) {
		auto C = comps[i];
		if (C.left_x <= 0 && 0 <= C.right_x) {
			int left_y = C.bottom.eval_x(0);
			int right_y = C.top.eval_x(0);
			if (left_y <= 0 && 0 <= right_y) {
				column mid_col(0, left_y, right_y, 0, 0, 0);
				auto p_left = move_left(mid_col, C.bottom, C.top, 0, C.left_x, A, B);
				auto p_right = move_right(mid_col, C.bottom, C.top, 0, C.right_x, A, B);
				comps[i].left_col = p_left.second;
				comps[i].right_col = p_right.second;
				comps[i].sum = (p_left.first + p_right.first + mod - mid_col.calc(A, B)) % mod;
				root = i;
				break;
			}
		}
	}
	dfs(root, -1, A, B);
	long long res = 0;
	for (auto C: comps) {
		res += C.sum;
		res %= mod;
	}
	return res;
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 629 ms 67540 KB Output is correct
2 Correct 629 ms 67788 KB Output is correct
3 Correct 605 ms 67568 KB Output is correct
4 Correct 631 ms 67656 KB Output is correct
5 Correct 623 ms 67520 KB Output is correct
6 Correct 598 ms 67692 KB Output is correct
7 Correct 618 ms 67688 KB Output is correct
8 Correct 630 ms 67708 KB Output is correct
9 Correct 630 ms 67564 KB Output is correct
10 Correct 635 ms 67544 KB Output is correct
11 Correct 616 ms 67780 KB Output is correct
12 Correct 603 ms 67672 KB Output is correct
13 Correct 614 ms 67812 KB Output is correct
14 Correct 616 ms 67664 KB Output is correct
15 Correct 623 ms 67680 KB Output is correct
16 Correct 651 ms 67560 KB Output is correct
17 Correct 634 ms 67536 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 7 ms 3176 KB Output is correct
3 Correct 2 ms 1032 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 4 ms 1804 KB Output is correct
6 Correct 8 ms 3204 KB Output is correct
7 Correct 26 ms 8120 KB Output is correct
8 Correct 2 ms 804 KB Output is correct
9 Correct 2 ms 684 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 48 ms 24568 KB Output is correct
12 Correct 29 ms 13332 KB Output is correct
13 Correct 23 ms 13124 KB Output is correct
14 Correct 49 ms 15808 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 216 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct

Subtask #5
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 7 ms 3176 KB Output is correct
5 Correct 2 ms 1032 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 5 ms 1804 KB Output is correct
8 Correct 9 ms 3204 KB Output is correct
9 Correct 27 ms 8076 KB Output is correct
10 Correct 2 ms 804 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 44 ms 24620 KB Output is correct
14 Correct 29 ms 13440 KB Output is correct
15 Correct 23 ms 13040 KB Output is correct
16 Correct 47 ms 15804 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 560 KB Output is correct
19 Correct 1 ms 300 KB Output is correct
20 Correct 71 ms 25860 KB Output is correct
21 Correct 7 ms 3204 KB Output is correct
22 Correct 4 ms 1772 KB Output is correct
23 Correct 92 ms 30468 KB Output is correct
24 Correct 160 ms 53588 KB Output is correct
25 Correct 158 ms 54232 KB Output is correct
26 Correct 90 ms 27036 KB Output is correct
27 Correct 76 ms 24044 KB Output is correct
28 Correct 46 ms 13680 KB Output is correct
29 Correct 210 ms 98140 KB Output is correct
30 Correct 109 ms 52748 KB Output is correct
31 Correct 106 ms 52800 KB Output is correct
32 Correct 225 ms 91236 KB Output is correct
33 Correct 76 ms 26056 KB Output is correct
34 Correct 25 ms 9548 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 1 ms 212 KB Output is correct

Subtask #6
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 616 ms 67660 KB Output is correct
2 Correct 604 ms 67676 KB Output is correct
3 Correct 599 ms 67800 KB Output is correct
4 Correct 607 ms 67764 KB Output is correct
5 Correct 612 ms 67512 KB Output is correct
6 Correct 599 ms 67648 KB Output is correct
7 Correct 610 ms 67568 KB Output is correct
8 Correct 610 ms 67556 KB Output is correct
9 Correct 618 ms 67664 KB Output is correct
10 Correct 609 ms 67884 KB Output is correct
11 Correct 617 ms 67628 KB Output is correct
12 Correct 611 ms 67792 KB Output is correct
13 Correct 611 ms 67564 KB Output is correct
14 Correct 611 ms 67572 KB Output is correct
15 Correct 647 ms 67780 KB Output is correct
16 Correct 618 ms 67652 KB Output is correct
17 Correct 609 ms 67668 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 7 ms 3176 KB Output is correct
20 Correct 2 ms 1032 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 5 ms 1740 KB Output is correct
23 Correct 8 ms 3204 KB Output is correct
24 Correct 28 ms 8124 KB Output is correct
25 Correct 2 ms 804 KB Output is correct
26 Correct 2 ms 724 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 43 ms 24496 KB Output is correct
29 Correct 29 ms 13440 KB Output is correct
30 Correct 26 ms 13096 KB Output is correct
31 Correct 51 ms 15804 KB Output is correct
32 Correct 1 ms 596 KB Output is correct
33 Correct 1 ms 556 KB Output is correct
34 Correct 2 ms 212 KB Output is correct
35 Correct 10 ms 3204 KB Output is correct
36 Correct 3 ms 804 KB Output is correct
37 Correct 4 ms 596 KB Output is correct
38 Correct 11 ms 3204 KB Output is correct
39 Correct 12 ms 3460 KB Output is correct
40 Correct 36 ms 12044 KB Output is correct
41 Correct 6 ms 932 KB Output is correct
42 Correct 6 ms 740 KB Output is correct
43 Correct 5 ms 596 KB Output is correct
44 Correct 63 ms 31200 KB Output is correct
45 Correct 36 ms 17196 KB Output is correct
46 Correct 36 ms 16668 KB Output is correct
47 Correct 31 ms 13612 KB Output is correct
48 Correct 7 ms 876 KB Output is correct
49 Correct 6 ms 596 KB Output is correct
50 Correct 1 ms 300 KB Output is correct
51 Correct 1 ms 216 KB Output is correct
52 Correct 1 ms 216 KB Output is correct
53 Correct 0 ms 212 KB Output is correct
54 Correct 1 ms 304 KB Output is correct
55 Correct 0 ms 304 KB Output is correct
56 Correct 0 ms 212 KB Output is correct
57 Correct 0 ms 212 KB Output is correct

Subtask #7
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Execution timed out 2092 ms 212 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 600 ms 67564 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 627 ms 67532 KB Output is correct
7 Correct 610 ms 67548 KB Output is correct
8 Correct 707 ms 67676 KB Output is correct
9 Correct 670 ms 67668 KB Output is correct
10 Correct 628 ms 67652 KB Output is correct
11 Correct 612 ms 67664 KB Output is correct
12 Correct 624 ms 67568 KB Output is correct
13 Correct 648 ms 67564 KB Output is correct
14 Correct 647 ms 67648 KB Output is correct
15 Correct 627 ms 67640 KB Output is correct
16 Correct 611 ms 67520 KB Output is correct
17 Correct 651 ms 67664 KB Output is correct
18 Correct 615 ms 67532 KB Output is correct
19 Correct 628 ms 67652 KB Output is correct
20 Correct 627 ms 67564 KB Output is correct
21 Correct 651 ms 67644 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 7 ms 3176 KB Output is correct
24 Correct 2 ms 1032 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 4 ms 1804 KB Output is correct
27 Correct 8 ms 3204 KB Output is correct
28 Correct 28 ms 8124 KB Output is correct
29 Correct 2 ms 804 KB Output is correct
30 Correct 1 ms 724 KB Output is correct
31 Correct 1 ms 492 KB Output is correct
32 Correct 48 ms 24544 KB Output is correct
33 Correct 30 ms 13272 KB Output is correct
34 Correct 25 ms 12992 KB Output is correct
35 Correct 49 ms 15724 KB Output is correct
36 Correct 1 ms 596 KB Output is correct
37 Correct 1 ms 556 KB Output is correct
38 Correct 1 ms 296 KB Output is correct
39 Correct 75 ms 25788 KB Output is correct
40 Correct 8 ms 3164 KB Output is correct
41 Correct 3 ms 1740 KB Output is correct
42 Correct 93 ms 30424 KB Output is correct
43 Correct 157 ms 53056 KB Output is correct
44 Correct 156 ms 53804 KB Output is correct
45 Correct 110 ms 27172 KB Output is correct
46 Correct 78 ms 23776 KB Output is correct
47 Correct 50 ms 13372 KB Output is correct
48 Correct 216 ms 97800 KB Output is correct
49 Correct 112 ms 52352 KB Output is correct
50 Correct 105 ms 52372 KB Output is correct
51 Correct 217 ms 90828 KB Output is correct
52 Correct 72 ms 25968 KB Output is correct
53 Correct 26 ms 9412 KB Output is correct
54 Correct 2 ms 212 KB Output is correct
55 Correct 10 ms 3204 KB Output is correct
56 Correct 3 ms 804 KB Output is correct
57 Correct 4 ms 596 KB Output is correct
58 Correct 10 ms 3176 KB Output is correct
59 Correct 12 ms 3556 KB Output is correct
60 Correct 36 ms 12088 KB Output is correct
61 Correct 7 ms 980 KB Output is correct
62 Correct 5 ms 776 KB Output is correct
63 Correct 5 ms 560 KB Output is correct
64 Correct 60 ms 31148 KB Output is correct
65 Correct 35 ms 17196 KB Output is correct
66 Correct 36 ms 16648 KB Output is correct
67 Correct 33 ms 13508 KB Output is correct
68 Correct 7 ms 780 KB Output is correct
69 Correct 7 ms 596 KB Output is correct
70 Execution timed out 2084 ms 212 KB Time limit exceeded
71 Halted 0 ms 0 KB -