oj.uz

Submission #571765

# Submission time Handle Problem Language Result Execution time Memory
571765 2022-06-02T16:42:50 Z 8e7 IOI Fever (JOI21_fever) C++17
100 / 100
 697 ms 57520 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk 
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define x first
#define y second
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1e9 + 7;

struct pnt{
	int x, y, id;
	pnt(){x = y = id = 0;}
	pnt(int a, int b, int c){x = a, y = b, id = c;}
	bool operator ==(const pnt &p){return x == p.x && y == p.y && id == p.id;}
};
pnt a[maxn];
vector<pnt> horz[4][maxn], vert[4][maxn], ru[4][maxn], rd[4][maxn];
bool cmp(const pnt &p, const pnt &q) {
	return p.x == q.x ? (q.y == p.y ? p.id < q.id : p.y < q.y) : p.x < q.x;
}
int LB(vector<pnt> &v, pnt P) {
	return lower_bound(v.begin(), v.end(), P, cmp) - v.begin();
}
int UB(vector<pnt> &v, pnt P) {
	return upper_bound(v.begin(), v.end(), P, cmp) - v.begin();
}
int mov[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int movru[4][2] = {{1, 1}, {1, 1}, {-1, -1}, {-1, -1}};
int movrd[4][2] = {{1, -1}, {-1, 1}, {-1, 1}, {1, -1}};

int mind[maxn][3], di[maxn];
bool vis[maxn];

int hi[maxn], vi[maxn], rui[maxn], rdi[maxn];
int main() {
	io
		int n;
	cin >> n;
	{
		vector<int> h, v, u, d;
		for (int i = 0;i < n;i++) {
			cin >> a[i].x >> a[i].y;
			a[i].id = i;
			a[i].x *= 2, a[i].y *= 2;
			h.push_back(a[i].y);
			v.push_back(a[i].x);
			u.push_back(a[i].x - a[i].y);
			d.push_back(a[i].x + a[i].y);
		}
		auto rs = [&] (vector<int> &ve) {
			sort(ve.begin(), ve.end());
			ve.resize(int(unique(ve.begin(), ve.end()) - ve.begin()));
		};
		rs(h), rs(v), rs(u), rs(d);
		for (int i = 0;i < n;i++) {
			hi[i] = lower_bound(h.begin(), h.end(), a[i].y) - h.begin();	
			vi[i] = lower_bound(v.begin(), v.end(), a[i].x) - v.begin();	
			rui[i] = lower_bound(u.begin(), u.end(), a[i].x - a[i].y) - u.begin();	
			rdi[i] = lower_bound(d.begin(), d.end(), a[i].x + a[i].y) - d.begin();	
		}
	}
	int ans = 0;
	for (int init_d = 0;init_d < 4;init_d++) {
		for (int i = 0;i < 4;i++) {
			for (int j = 0;j < maxn;j++)  {
				horz[i][j].clear(), vert[i][j].clear(), ru[i][j].clear(), rd[i][j].clear();
			}
		}
		for (int i = 0;i < n;i++) {
			mind[i][0] = mind[i][1] = mind[i][2] = inf;
			vis[i] = 0;
			if (i == 0) continue;
			int dx = a[i].x - a[0].x, dy = a[i].y - a[0].y;
			if (abs(dx) > abs(dy)) {
				di[i] = dx > 0 ? 2 : 0;
			} else if (abs(dx) < abs(dy)) {
				di[i] = dy > 0 ? 3 : 1;
			} else {
				pii tmp = {dx, dy};		
				for (int j = 0;j < 4 - init_d;j++) tmp = {-tmp.y, tmp.x};
				if (tmp.x > 0) di[i] = tmp.y > 0 ? 3 : 1;
				else di[i] = 0;
				di[i] = (di[i] + init_d)%4;
			}
			if (di[i] % 2) {
				vert[di[i]][vi[i]].push_back(a[i]);
			} else {
				horz[di[i]][hi[i]].push_back(a[i]);
			}
			ru[di[i]][rui[i]].push_back(a[i]);
			rd[di[i]][rdi[i]].push_back(a[i]);
		}
		for (int i = 0;i < 4;i++) {
			for (int j = 0;j < maxn;j++) {
				sort(horz[i][j].begin(), horz[i][j].end(), cmp);
				sort(vert[i][j].begin(), vert[i][j].end(), cmp);
				sort(ru[i][j].begin(), ru[i][j].end(), cmp);
				sort(rd[i][j].begin(), rd[i][j].end(), cmp);
			}
		}
		mind[0][0] = 0;
		di[0] = init_d;


		auto col = [&] (int i, int j) {
			int dx = a[j].x - a[i].x, dy = a[j].y - a[i].y;			
			int divx = mov[di[i]][0] - mov[di[j]][0], divy = mov[di[i]][1] - mov[di[j]][1];
			if (dx && divx == 0) return -1;	
			if (dy && divy == 0) return -1;	
			if (dx == 0) {
				if (abs(di[i] - di[j]) == 2) return dy / divy;
				return -1;
			}
			if (dy == 0) {
				if (abs(di[i] - di[j]) == 2) return dx / divx;
				return -1;
			}
			if (dx * divy != dy * divx) return -1;
			return dx / divx;
		};


		priority_queue<pii, vector<pii>, greater<pii> > pq;
		pq.push({0, 0});
		pnt cur;
		int id, prv = 0, ti;

		auto relax = [&](pnt p, int d, int val) {
			int ind = p.id;
			if (val >= ti && val < mind[ind][d]) {
				mind[ind][d] = val;
				pq.push({val, ind * 3 + d});
			}
		};
		auto upd = [&] (vector<pnt> &se, int it, int d, bool type) {
			pnt p;
			if (type == 0) {
				if (it) {
					p = se[it-1];
				} else {
					return;
				}
			} else {
				if (it != se.size()) {
					p = se[it];
				} else {
					return;
				}
			}
			relax(p, d, col(id, p.id));
		};
		auto to = [&] (vector<pnt> &se, bool type) { //0:prev, 1:next
			int it = LB(se, cur);
			pnt q;	
			if (type && it+1 != se.size()) {
				q = se[it+1];	
			} else if (type == 0 && it) {
				q = se[it-1];
			}
			int val = (abs(q.y - cur.y) + abs(q.x - cur.x)) / 2;
			relax(q, prv, ti + val);
		};

		while (pq.size()) {
			id = pq.top().ss / 3, prv = pq.top().ss % 3;
			ti = pq.top().ff;
			pq.pop();
			if (ti != mind[id][prv]) continue;
			cur = a[id];
			int dir = di[id];
			if (!vis[id]) {

				pnt pos = pnt(cur.x + mov[dir][0] * 2 * ti, cur.y + mov[dir][1] * 2 * ti, -1);
				if (dir % 2 == 0) {
					auto &se = horz[(dir+2)%4][hi[id]];
					if (dir == 0) upd(se, LB(se, pos), 0, 1);
					else upd(se, UB(se, pos), 0, 0);
				} else {
					auto &se = vert[(dir+2)%4][vi[id]];
					if (dir == 1) upd(se, LB(se, pos), 0, 1);
					else upd(se, UB(se, pos), 0, 0);
				}
				{
					pos = pnt(cur.x + movru[dir][0] * ti, cur.y + movru[dir][1] * ti, -1);
					auto &se = ru[(3 - dir)][rui[id]];
					if (dir < 2) upd(se, LB(se, pos), 1, 1);
					else upd(se, UB(se, pos), 1, 0);
				}

				{
					pos = pnt(cur.x + movrd[dir][0] * ti, cur.y + movrd[dir][1] * ti, -1);
					auto se = rd[(dir < 2 ? 1 - dir : 5 - dir)][rdi[id]];
					if (dir == 0 || dir == 3) upd(se, LB(se, pos), 2, 1);	
					else upd(se, UB(se, pos), 2, 0);	
				}
			}
			vis[id] = 1;

			if (id == 0) continue;
			if (prv == 0) {
				if (dir % 2 == 0) to(horz[dir][hi[id]], dir == 2);
				else to(vert[dir][vi[id]], dir == 3);
			} else if (prv == 1) {
				to(ru[dir][rui[id]], dir >= 2);
			} else {
				to(rd[dir][rdi[id]], dir == 1 || dir == 2);
			}
		}
		int cnt = 0;
		for (int i = 0;i < n;i++) {
			if (vis[i]) cnt++;
		}
		ans = max(ans, cnt);
	}
	cout << ans << "\n";
}

Compilation message

fever.cpp: In lambda function:
fever.cpp:160:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pnt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |     if (it != se.size()) {
      |         ~~~^~~~~~~~~~~~
fever.cpp: In lambda function:
fever.cpp:171:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pnt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |    if (type && it+1 != se.size()) {
      |                ~~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 39116 KB Output is correct
2 Correct 34 ms 39080 KB Output is correct
3 Correct 33 ms 39080 KB Output is correct
4 Correct 41 ms 39088 KB Output is correct
5 Correct 40 ms 39052 KB Output is correct
6 Correct 32 ms 39084 KB Output is correct
7 Correct 35 ms 39108 KB Output is correct
8 Correct 33 ms 39080 KB Output is correct
9 Correct 37 ms 39100 KB Output is correct
10 Correct 32 ms 39080 KB Output is correct
11 Correct 34 ms 39072 KB Output is correct
12 Correct 33 ms 39060 KB Output is correct
13 Correct 38 ms 39080 KB Output is correct
14 Correct 37 ms 39088 KB Output is correct
15 Correct 38 ms 39088 KB Output is correct
16 Correct 38 ms 39076 KB Output is correct
17 Correct 33 ms 39000 KB Output is correct
18 Correct 34 ms 39072 KB Output is correct
19 Correct 35 ms 39080 KB Output is correct
20 Correct 34 ms 38996 KB Output is correct
21 Correct 34 ms 39020 KB Output is correct
22 Correct 34 ms 39012 KB Output is correct
23 Correct 34 ms 38996 KB Output is correct
24 Correct 34 ms 39104 KB Output is correct
25 Correct 34 ms 38996 KB Output is correct
26 Correct 34 ms 39272 KB Output is correct
27 Correct 34 ms 38996 KB Output is correct
28 Correct 35 ms 39092 KB Output is correct
29 Correct 36 ms 39032 KB Output is correct
30 Correct 36 ms 38968 KB Output is correct
31 Correct 35 ms 39080 KB Output is correct
32 Correct 34 ms 38996 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 39116 KB Output is correct
2 Correct 34 ms 39080 KB Output is correct
3 Correct 33 ms 39080 KB Output is correct
4 Correct 41 ms 39088 KB Output is correct
5 Correct 40 ms 39052 KB Output is correct
6 Correct 32 ms 39084 KB Output is correct
7 Correct 35 ms 39108 KB Output is correct
8 Correct 33 ms 39080 KB Output is correct
9 Correct 37 ms 39100 KB Output is correct
10 Correct 32 ms 39080 KB Output is correct
11 Correct 34 ms 39072 KB Output is correct
12 Correct 33 ms 39060 KB Output is correct
13 Correct 38 ms 39080 KB Output is correct
14 Correct 37 ms 39088 KB Output is correct
15 Correct 38 ms 39088 KB Output is correct
16 Correct 38 ms 39076 KB Output is correct
17 Correct 33 ms 39000 KB Output is correct
18 Correct 34 ms 39072 KB Output is correct
19 Correct 35 ms 39080 KB Output is correct
20 Correct 34 ms 38996 KB Output is correct
21 Correct 34 ms 39020 KB Output is correct
22 Correct 34 ms 39012 KB Output is correct
23 Correct 34 ms 38996 KB Output is correct
24 Correct 34 ms 39104 KB Output is correct
25 Correct 34 ms 38996 KB Output is correct
26 Correct 34 ms 39272 KB Output is correct
27 Correct 34 ms 38996 KB Output is correct
28 Correct 35 ms 39092 KB Output is correct
29 Correct 36 ms 39032 KB Output is correct
30 Correct 36 ms 38968 KB Output is correct
31 Correct 35 ms 39080 KB Output is correct
32 Correct 34 ms 38996 KB Output is correct
33 Correct 33 ms 38996 KB Output is correct
34 Correct 45 ms 39072 KB Output is correct
35 Correct 43 ms 39084 KB Output is correct
36 Correct 37 ms 39100 KB Output is correct
37 Correct 33 ms 38988 KB Output is correct
38 Correct 33 ms 39016 KB Output is correct
39 Correct 36 ms 39076 KB Output is correct
40 Correct 33 ms 39048 KB Output is correct
41 Correct 35 ms 39156 KB Output is correct
42 Correct 36 ms 39080 KB Output is correct
43 Correct 35 ms 39080 KB Output is correct
44 Correct 37 ms 39004 KB Output is correct
45 Correct 36 ms 38984 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 39096 KB Output is correct
2 Correct 34 ms 39092 KB Output is correct
3 Correct 35 ms 39108 KB Output is correct
4 Correct 36 ms 39116 KB Output is correct
5 Correct 35 ms 39116 KB Output is correct
6 Correct 33 ms 38996 KB Output is correct
7 Correct 37 ms 39104 KB Output is correct
8 Correct 33 ms 39068 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 39116 KB Output is correct
2 Correct 34 ms 39080 KB Output is correct
3 Correct 33 ms 39080 KB Output is correct
4 Correct 41 ms 39088 KB Output is correct
5 Correct 40 ms 39052 KB Output is correct
6 Correct 32 ms 39084 KB Output is correct
7 Correct 35 ms 39108 KB Output is correct
8 Correct 33 ms 39080 KB Output is correct
9 Correct 37 ms 39100 KB Output is correct
10 Correct 32 ms 39080 KB Output is correct
11 Correct 34 ms 39072 KB Output is correct
12 Correct 33 ms 39060 KB Output is correct
13 Correct 38 ms 39080 KB Output is correct
14 Correct 37 ms 39088 KB Output is correct
15 Correct 38 ms 39088 KB Output is correct
16 Correct 38 ms 39076 KB Output is correct
17 Correct 33 ms 39000 KB Output is correct
18 Correct 34 ms 39072 KB Output is correct
19 Correct 35 ms 39080 KB Output is correct
20 Correct 34 ms 38996 KB Output is correct
21 Correct 34 ms 39020 KB Output is correct
22 Correct 34 ms 39012 KB Output is correct
23 Correct 34 ms 38996 KB Output is correct
24 Correct 34 ms 39104 KB Output is correct
25 Correct 34 ms 38996 KB Output is correct
26 Correct 34 ms 39272 KB Output is correct
27 Correct 34 ms 38996 KB Output is correct
28 Correct 35 ms 39092 KB Output is correct
29 Correct 36 ms 39032 KB Output is correct
30 Correct 36 ms 38968 KB Output is correct
31 Correct 35 ms 39080 KB Output is correct
32 Correct 34 ms 38996 KB Output is correct
33 Correct 33 ms 38996 KB Output is correct
34 Correct 45 ms 39072 KB Output is correct
35 Correct 43 ms 39084 KB Output is correct
36 Correct 37 ms 39100 KB Output is correct
37 Correct 33 ms 38988 KB Output is correct
38 Correct 33 ms 39016 KB Output is correct
39 Correct 36 ms 39076 KB Output is correct
40 Correct 33 ms 39048 KB Output is correct
41 Correct 35 ms 39156 KB Output is correct
42 Correct 36 ms 39080 KB Output is correct
43 Correct 35 ms 39080 KB Output is correct
44 Correct 37 ms 39004 KB Output is correct
45 Correct 36 ms 38984 KB Output is correct
46 Correct 34 ms 39096 KB Output is correct
47 Correct 34 ms 39092 KB Output is correct
48 Correct 35 ms 39108 KB Output is correct
49 Correct 36 ms 39116 KB Output is correct
50 Correct 35 ms 39116 KB Output is correct
51 Correct 33 ms 38996 KB Output is correct
52 Correct 37 ms 39104 KB Output is correct
53 Correct 33 ms 39068 KB Output is correct
54 Correct 35 ms 39096 KB Output is correct
55 Correct 35 ms 39068 KB Output is correct
56 Correct 35 ms 39096 KB Output is correct
57 Correct 34 ms 39072 KB Output is correct
58 Correct 36 ms 39196 KB Output is correct
59 Correct 34 ms 39096 KB Output is correct
60 Correct 35 ms 38996 KB Output is correct
61 Correct 33 ms 39100 KB Output is correct
62 Correct 34 ms 39132 KB Output is correct
63 Correct 33 ms 39112 KB Output is correct
64 Correct 33 ms 39072 KB Output is correct
65 Correct 32 ms 38996 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 39116 KB Output is correct
2 Correct 34 ms 39080 KB Output is correct
3 Correct 33 ms 39080 KB Output is correct
4 Correct 41 ms 39088 KB Output is correct
5 Correct 40 ms 39052 KB Output is correct
6 Correct 32 ms 39084 KB Output is correct
7 Correct 35 ms 39108 KB Output is correct
8 Correct 33 ms 39080 KB Output is correct
9 Correct 37 ms 39100 KB Output is correct
10 Correct 32 ms 39080 KB Output is correct
11 Correct 34 ms 39072 KB Output is correct
12 Correct 33 ms 39060 KB Output is correct
13 Correct 38 ms 39080 KB Output is correct
14 Correct 37 ms 39088 KB Output is correct
15 Correct 38 ms 39088 KB Output is correct
16 Correct 38 ms 39076 KB Output is correct
17 Correct 33 ms 39000 KB Output is correct
18 Correct 34 ms 39072 KB Output is correct
19 Correct 35 ms 39080 KB Output is correct
20 Correct 34 ms 38996 KB Output is correct
21 Correct 34 ms 39020 KB Output is correct
22 Correct 34 ms 39012 KB Output is correct
23 Correct 34 ms 38996 KB Output is correct
24 Correct 34 ms 39104 KB Output is correct
25 Correct 34 ms 38996 KB Output is correct
26 Correct 34 ms 39272 KB Output is correct
27 Correct 34 ms 38996 KB Output is correct
28 Correct 35 ms 39092 KB Output is correct
29 Correct 36 ms 39032 KB Output is correct
30 Correct 36 ms 38968 KB Output is correct
31 Correct 35 ms 39080 KB Output is correct
32 Correct 34 ms 38996 KB Output is correct
33 Correct 33 ms 38996 KB Output is correct
34 Correct 45 ms 39072 KB Output is correct
35 Correct 43 ms 39084 KB Output is correct
36 Correct 37 ms 39100 KB Output is correct
37 Correct 33 ms 38988 KB Output is correct
38 Correct 33 ms 39016 KB Output is correct
39 Correct 36 ms 39076 KB Output is correct
40 Correct 33 ms 39048 KB Output is correct
41 Correct 35 ms 39156 KB Output is correct
42 Correct 36 ms 39080 KB Output is correct
43 Correct 35 ms 39080 KB Output is correct
44 Correct 37 ms 39004 KB Output is correct
45 Correct 36 ms 38984 KB Output is correct
46 Correct 34 ms 39096 KB Output is correct
47 Correct 34 ms 39092 KB Output is correct
48 Correct 35 ms 39108 KB Output is correct
49 Correct 36 ms 39116 KB Output is correct
50 Correct 35 ms 39116 KB Output is correct
51 Correct 33 ms 38996 KB Output is correct
52 Correct 37 ms 39104 KB Output is correct
53 Correct 33 ms 39068 KB Output is correct
54 Correct 35 ms 39096 KB Output is correct
55 Correct 35 ms 39068 KB Output is correct
56 Correct 35 ms 39096 KB Output is correct
57 Correct 34 ms 39072 KB Output is correct
58 Correct 36 ms 39196 KB Output is correct
59 Correct 34 ms 39096 KB Output is correct
60 Correct 35 ms 38996 KB Output is correct
61 Correct 33 ms 39100 KB Output is correct
62 Correct 34 ms 39132 KB Output is correct
63 Correct 33 ms 39112 KB Output is correct
64 Correct 33 ms 39072 KB Output is correct
65 Correct 32 ms 38996 KB Output is correct
66 Correct 37 ms 39372 KB Output is correct
67 Correct 39 ms 39396 KB Output is correct
68 Correct 38 ms 39532 KB Output is correct
69 Correct 45 ms 39396 KB Output is correct
70 Correct 38 ms 39404 KB Output is correct
71 Correct 36 ms 39380 KB Output is correct
72 Correct 37 ms 39368 KB Output is correct
73 Correct 37 ms 39408 KB Output is correct
74 Correct 37 ms 39664 KB Output is correct
75 Correct 41 ms 39696 KB Output is correct
76 Correct 38 ms 39496 KB Output is correct
77 Correct 37 ms 39420 KB Output is correct
78 Correct 37 ms 39380 KB Output is correct
79 Correct 38 ms 39508 KB Output is correct
80 Correct 36 ms 39408 KB Output is correct
81 Correct 37 ms 39484 KB Output is correct
82 Correct 37 ms 39476 KB Output is correct
83 Correct 39 ms 39492 KB Output is correct
84 Correct 34 ms 39380 KB Output is correct
85 Correct 34 ms 39380 KB Output is correct
86 Correct 35 ms 39400 KB Output is correct
87 Correct 33 ms 39332 KB Output is correct
88 Correct 36 ms 39564 KB Output is correct
89 Correct 38 ms 39452 KB Output is correct
90 Correct 40 ms 39508 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 39116 KB Output is correct
2 Correct 34 ms 39080 KB Output is correct
3 Correct 33 ms 39080 KB Output is correct
4 Correct 41 ms 39088 KB Output is correct
5 Correct 40 ms 39052 KB Output is correct
6 Correct 32 ms 39084 KB Output is correct
7 Correct 35 ms 39108 KB Output is correct
8 Correct 33 ms 39080 KB Output is correct
9 Correct 37 ms 39100 KB Output is correct
10 Correct 32 ms 39080 KB Output is correct
11 Correct 34 ms 39072 KB Output is correct
12 Correct 33 ms 39060 KB Output is correct
13 Correct 38 ms 39080 KB Output is correct
14 Correct 37 ms 39088 KB Output is correct
15 Correct 38 ms 39088 KB Output is correct
16 Correct 38 ms 39076 KB Output is correct
17 Correct 33 ms 39000 KB Output is correct
18 Correct 34 ms 39072 KB Output is correct
19 Correct 35 ms 39080 KB Output is correct
20 Correct 34 ms 38996 KB Output is correct
21 Correct 34 ms 39020 KB Output is correct
22 Correct 34 ms 39012 KB Output is correct
23 Correct 34 ms 38996 KB Output is correct
24 Correct 34 ms 39104 KB Output is correct
25 Correct 34 ms 38996 KB Output is correct
26 Correct 34 ms 39272 KB Output is correct
27 Correct 34 ms 38996 KB Output is correct
28 Correct 35 ms 39092 KB Output is correct
29 Correct 36 ms 39032 KB Output is correct
30 Correct 36 ms 38968 KB Output is correct
31 Correct 35 ms 39080 KB Output is correct
32 Correct 34 ms 38996 KB Output is correct
33 Correct 33 ms 38996 KB Output is correct
34 Correct 45 ms 39072 KB Output is correct
35 Correct 43 ms 39084 KB Output is correct
36 Correct 37 ms 39100 KB Output is correct
37 Correct 33 ms 38988 KB Output is correct
38 Correct 33 ms 39016 KB Output is correct
39 Correct 36 ms 39076 KB Output is correct
40 Correct 33 ms 39048 KB Output is correct
41 Correct 35 ms 39156 KB Output is correct
42 Correct 36 ms 39080 KB Output is correct
43 Correct 35 ms 39080 KB Output is correct
44 Correct 37 ms 39004 KB Output is correct
45 Correct 36 ms 38984 KB Output is correct
46 Correct 34 ms 39096 KB Output is correct
47 Correct 34 ms 39092 KB Output is correct
48 Correct 35 ms 39108 KB Output is correct
49 Correct 36 ms 39116 KB Output is correct
50 Correct 35 ms 39116 KB Output is correct
51 Correct 33 ms 38996 KB Output is correct
52 Correct 37 ms 39104 KB Output is correct
53 Correct 33 ms 39068 KB Output is correct
54 Correct 35 ms 39096 KB Output is correct
55 Correct 35 ms 39068 KB Output is correct
56 Correct 35 ms 39096 KB Output is correct
57 Correct 34 ms 39072 KB Output is correct
58 Correct 36 ms 39196 KB Output is correct
59 Correct 34 ms 39096 KB Output is correct
60 Correct 35 ms 38996 KB Output is correct
61 Correct 33 ms 39100 KB Output is correct
62 Correct 34 ms 39132 KB Output is correct
63 Correct 33 ms 39112 KB Output is correct
64 Correct 33 ms 39072 KB Output is correct
65 Correct 32 ms 38996 KB Output is correct
66 Correct 236 ms 48752 KB Output is correct
67 Correct 288 ms 50868 KB Output is correct
68 Correct 285 ms 51940 KB Output is correct
69 Correct 262 ms 57428 KB Output is correct
70 Correct 334 ms 57520 KB Output is correct
71 Correct 311 ms 53476 KB Output is correct
72 Correct 298 ms 53116 KB Output is correct
73 Correct 262 ms 51972 KB Output is correct
74 Correct 291 ms 53600 KB Output is correct
75 Correct 302 ms 53608 KB Output is correct
76 Correct 263 ms 51972 KB Output is correct
77 Correct 309 ms 53504 KB Output is correct
78 Correct 305 ms 53472 KB Output is correct
79 Correct 302 ms 53512 KB Output is correct

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 39116 KB Output is correct
2 Correct 34 ms 39080 KB Output is correct
3 Correct 33 ms 39080 KB Output is correct
4 Correct 41 ms 39088 KB Output is correct
5 Correct 40 ms 39052 KB Output is correct
6 Correct 32 ms 39084 KB Output is correct
7 Correct 35 ms 39108 KB Output is correct
8 Correct 33 ms 39080 KB Output is correct
9 Correct 37 ms 39100 KB Output is correct
10 Correct 32 ms 39080 KB Output is correct
11 Correct 34 ms 39072 KB Output is correct
12 Correct 33 ms 39060 KB Output is correct
13 Correct 38 ms 39080 KB Output is correct
14 Correct 37 ms 39088 KB Output is correct
15 Correct 38 ms 39088 KB Output is correct
16 Correct 38 ms 39076 KB Output is correct
17 Correct 33 ms 39000 KB Output is correct
18 Correct 34 ms 39072 KB Output is correct
19 Correct 35 ms 39080 KB Output is correct
20 Correct 34 ms 38996 KB Output is correct
21 Correct 34 ms 39020 KB Output is correct
22 Correct 34 ms 39012 KB Output is correct
23 Correct 34 ms 38996 KB Output is correct
24 Correct 34 ms 39104 KB Output is correct
25 Correct 34 ms 38996 KB Output is correct
26 Correct 34 ms 39272 KB Output is correct
27 Correct 34 ms 38996 KB Output is correct
28 Correct 35 ms 39092 KB Output is correct
29 Correct 36 ms 39032 KB Output is correct
30 Correct 36 ms 38968 KB Output is correct
31 Correct 35 ms 39080 KB Output is correct
32 Correct 34 ms 38996 KB Output is correct
33 Correct 33 ms 38996 KB Output is correct
34 Correct 45 ms 39072 KB Output is correct
35 Correct 43 ms 39084 KB Output is correct
36 Correct 37 ms 39100 KB Output is correct
37 Correct 33 ms 38988 KB Output is correct
38 Correct 33 ms 39016 KB Output is correct
39 Correct 36 ms 39076 KB Output is correct
40 Correct 33 ms 39048 KB Output is correct
41 Correct 35 ms 39156 KB Output is correct
42 Correct 36 ms 39080 KB Output is correct
43 Correct 35 ms 39080 KB Output is correct
44 Correct 37 ms 39004 KB Output is correct
45 Correct 36 ms 38984 KB Output is correct
46 Correct 34 ms 39096 KB Output is correct
47 Correct 34 ms 39092 KB Output is correct
48 Correct 35 ms 39108 KB Output is correct
49 Correct 36 ms 39116 KB Output is correct
50 Correct 35 ms 39116 KB Output is correct
51 Correct 33 ms 38996 KB Output is correct
52 Correct 37 ms 39104 KB Output is correct
53 Correct 33 ms 39068 KB Output is correct
54 Correct 35 ms 39096 KB Output is correct
55 Correct 35 ms 39068 KB Output is correct
56 Correct 35 ms 39096 KB Output is correct
57 Correct 34 ms 39072 KB Output is correct
58 Correct 36 ms 39196 KB Output is correct
59 Correct 34 ms 39096 KB Output is correct
60 Correct 35 ms 38996 KB Output is correct
61 Correct 33 ms 39100 KB Output is correct
62 Correct 34 ms 39132 KB Output is correct
63 Correct 33 ms 39112 KB Output is correct
64 Correct 33 ms 39072 KB Output is correct
65 Correct 32 ms 38996 KB Output is correct
66 Correct 37 ms 39372 KB Output is correct
67 Correct 39 ms 39396 KB Output is correct
68 Correct 38 ms 39532 KB Output is correct
69 Correct 45 ms 39396 KB Output is correct
70 Correct 38 ms 39404 KB Output is correct
71 Correct 36 ms 39380 KB Output is correct
72 Correct 37 ms 39368 KB Output is correct
73 Correct 37 ms 39408 KB Output is correct
74 Correct 37 ms 39664 KB Output is correct
75 Correct 41 ms 39696 KB Output is correct
76 Correct 38 ms 39496 KB Output is correct
77 Correct 37 ms 39420 KB Output is correct
78 Correct 37 ms 39380 KB Output is correct
79 Correct 38 ms 39508 KB Output is correct
80 Correct 36 ms 39408 KB Output is correct
81 Correct 37 ms 39484 KB Output is correct
82 Correct 37 ms 39476 KB Output is correct
83 Correct 39 ms 39492 KB Output is correct
84 Correct 34 ms 39380 KB Output is correct
85 Correct 34 ms 39380 KB Output is correct
86 Correct 35 ms 39400 KB Output is correct
87 Correct 33 ms 39332 KB Output is correct
88 Correct 36 ms 39564 KB Output is correct
89 Correct 38 ms 39452 KB Output is correct
90 Correct 40 ms 39508 KB Output is correct
91 Correct 236 ms 48752 KB Output is correct
92 Correct 288 ms 50868 KB Output is correct
93 Correct 285 ms 51940 KB Output is correct
94 Correct 262 ms 57428 KB Output is correct
95 Correct 334 ms 57520 KB Output is correct
96 Correct 311 ms 53476 KB Output is correct
97 Correct 298 ms 53116 KB Output is correct
98 Correct 262 ms 51972 KB Output is correct
99 Correct 291 ms 53600 KB Output is correct
100 Correct 302 ms 53608 KB Output is correct
101 Correct 263 ms 51972 KB Output is correct
102 Correct 309 ms 53504 KB Output is correct
103 Correct 305 ms 53472 KB Output is correct
104 Correct 302 ms 53512 KB Output is correct
105 Correct 330 ms 46768 KB Output is correct
106 Correct 402 ms 48744 KB Output is correct
107 Correct 697 ms 49216 KB Output is correct
108 Correct 429 ms 49032 KB Output is correct
109 Correct 206 ms 49264 KB Output is correct
110 Correct 281 ms 51124 KB Output is correct
111 Correct 281 ms 53532 KB Output is correct
112 Correct 308 ms 52592 KB Output is correct
113 Correct 299 ms 52796 KB Output is correct
114 Correct 532 ms 49984 KB Output is correct
115 Correct 281 ms 51996 KB Output is correct
116 Correct 314 ms 52672 KB Output is correct
117 Correct 316 ms 52584 KB Output is correct
118 Correct 353 ms 50812 KB Output is correct
119 Correct 292 ms 52216 KB Output is correct
120 Correct 304 ms 52704 KB Output is correct
121 Correct 310 ms 53400 KB Output is correct
122 Correct 332 ms 53436 KB Output is correct
123 Correct 278 ms 51028 KB Output is correct
124 Correct 276 ms 51448 KB Output is correct
125 Correct 122 ms 47900 KB Output is correct
126 Correct 112 ms 49324 KB Output is correct
127 Correct 138 ms 49340 KB Output is correct
128 Correct 129 ms 49172 KB Output is correct
129 Correct 132 ms 48244 KB Output is correct