답안 #579030

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
579030	2022-06-18T10:14:08 Z	MetalPower	IOI 바이러스 (JOI21_fever)	C++14	69 / 100	2360 ms	90860 KB

fever

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define pli pair<ll, pii>
#define fi first
#define se second

const ll MX = 3e5 + 10;
const ll INF = 1e18;

ll N, X[MX], Y[MX], direction[MX];

// Right, Down, Left, Up

map<ll, vector<pii>> vert[4], hori[4], incd[4], decd[4];
ll dist[MX * 3]; bool colored[MX], vis[MX * 3];

vector<pii> adj[MX * 3];
// node, weight

void buildEdge(vector<pii>& v, ll inc, ll dir){ // dir 0 line, 1 clockwise, 2 counterclockwise
	if(inc == 1){
		for(ll i = 1; i < v.size(); i++){
			ll w = (v[i].fi - v[i - 1].fi) / (dir == 0 ? 2ll : 1ll);
			adj[(ll) 3 * v[i - 1].se + dir].push_back({(ll) 3 * v[i].se + dir, w});
		}
	}else{
		for(ll i = v.size() - 1; i > 0; i--){
			ll w = (v[i].fi - v[i - 1].fi) / (dir == 0 ? 2ll : 1ll);
			adj[(ll) 3 * v[i].se + dir].push_back({(ll) 3 * v[i - 1].se + dir, w});
		}
	}
}

ll absol(ll x){
	return x > 0 ? x : -x;
}

pii trav(vector<pii>& v, ll node, ll d, ll dir){
	ll idx = lower_bound(v.begin(), v.end(), make_pair(d, (ll) -1)) - v.begin();
	if(idx == v.size()) return make_pair(-1, 0);
	ll nxt = v[idx].se, mdist;
	mdist = (absol(X[node] - X[nxt]) + absol(Y[node] - Y[nxt])) / 2;
	return {nxt * 3 + dir, mdist};
}

pii dtrav(vector<pii>& v, ll node, ll d, ll dir){
	ll idx = lower_bound(v.begin(), v.end(), make_pair(d + 1, (ll) -1)) - v.begin() - 1;
	if(idx == -1) return make_pair(-1, 0);
	ll nxt = v[idx].se, mdist;
	mdist = (absol(X[node] - X[nxt]) + absol(Y[node] - Y[nxt])) / 2;
	return {nxt * 3 + dir, mdist};
}

ll solve(){

	memset(vis, 0, sizeof vis);
	for(ll i = 0; i < 3 * MX; i++){
		adj[i].clear();
		dist[i] = INF;
		if(i < MX) colored[i] = false;
	}

	direction[0] = 0;
	for(ll i = 1; i < N; i++){
		ll _x = X[i] / 2, _y = Y[i] / 2;
		if(_x < 0 && (_y <= 0 ? -_y <= -_x : _y <= -_x)) direction[i] = 0;
		else if(_y > 0 && (_x <= 0 ? -_x <= _y - 1 : _x <= _y)) direction[i] = 1;
		else if(_x > 0 && (_y <= 0 ? -_y <= _x - 1 : _y <= _x - 1)) direction[i] = 2;
		else if(_y < 0 && (_x <= 0 ? -_x <= -_y - 1 : _x <= -_y)) direction[i] = 3;
		else assert(false);
	}

	for(ll d = 0; d < 4; d++){
		vert[d].clear(), hori[d].clear(), incd[d].clear(), decd[d].clear();
	}

	for(ll i = 0; i < N; i++){
		vert[direction[i]][X[i]].push_back({Y[i], i});
		hori[direction[i]][Y[i]].push_back({X[i], i});
		incd[direction[i]][X[i] - Y[i]].push_back({X[i], i});
		decd[direction[i]][X[i] + Y[i]].push_back({X[i], i});
	}

	for(ll d = 0; d < 4; d++){
		for(auto& x : vert[d]) sort(x.se.begin(), x.se.end());
		for(auto& x : hori[d]) sort(x.se.begin(), x.se.end());
		for(auto& x : incd[d]) sort(x.se.begin(), x.se.end());
		for(auto& x : decd[d]) sort(x.se.begin(), x.se.end());
	}

	// Right, Down, Left, Up
	{
		for(auto& x : hori[0]) buildEdge(x.se, 0, 0);
		for(auto& x : vert[1]) buildEdge(x.se, 1, 0); 
		for(auto& x : hori[2]) buildEdge(x.se, 1, 0);
		for(auto& x : vert[3]) buildEdge(x.se, 0, 0);
	}

	{
		for(auto& x : incd[0]) buildEdge(x.se, 0, 2);
		for(auto& x : incd[1]) buildEdge(x.se, 1, 1);
		for(auto& x : incd[2]) buildEdge(x.se, 1, 2);
		for(auto& x : incd[3]) buildEdge(x.se, 0, 1);
	}

	{
		for(auto& x : decd[0]) buildEdge(x.se, 0, 1);
		for(auto& x : decd[1]) buildEdge(x.se, 0, 2);
		for(auto& x : decd[2]) buildEdge(x.se, 1, 1);
		for(auto& x : decd[3]) buildEdge(x.se, 1, 2);
	}

	priority_queue<pii, vector<pii>, greater<pii>> pq;

	pq.push({0, 0});
	dist[0] = 0;

	ll cnt = 0;

	while(!pq.empty()){

		// place-holder node
		ll cd = pq.top().fi; ll pd = pq.top().se; pq.pop();
		
		if(!vis[pd]){ // Reachable edge
			vis[pd] = true;
			for(auto nxt : adj[pd]){
				ll nd = cd + nxt.se;
				if(dist[nxt.fi] > nd){
					dist[nxt.fi] = nd;
					pq.push({dist[nxt.fi], nxt.fi});
				}
			}
		}

		// Right, Down, Left, Up

		ll node = pd / 3;
		if(!colored[node]){ // isColored
			// find collision

			pii nxt = {-1, 0};

			if(direction[node] == 0){

				nxt = trav(hori[2][Y[node]], node, X[node] + (ll) 2 * dist[pd], 0);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

				nxt = trav(incd[1][X[node] - Y[node]], node, X[node] + dist[pd], 1);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

				nxt = trav(decd[3][X[node] + Y[node]], node, X[node] + dist[pd], 2);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

			}else if(direction[node] == 1){

				nxt = dtrav(vert[3][X[node]], node, Y[node] - (ll) 2 * dist[pd], 0);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

				nxt = trav(decd[2][X[node] + Y[node]], node, X[node] + dist[pd], 1);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

				nxt = dtrav(incd[0][X[node] - Y[node]], node, X[node] - dist[pd], 2);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

			}else if(direction[node] == 2){

				nxt = dtrav(hori[0][Y[node]], node, X[node] - (ll) 2 * dist[pd], 0);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

				nxt = dtrav(incd[3][X[node] - Y[node]], node, X[node] - dist[pd], 1);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

				nxt = dtrav(decd[1][X[node] + Y[node]], node, X[node] - dist[pd], 2);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

			}else if(direction[node] == 3){

				nxt = trav(vert[1][X[node]], node, Y[node] + (ll) 2 * dist[pd], 0);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

				nxt = dtrav(decd[0][X[node] + Y[node]], node, X[node] - dist[pd], 1);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

				nxt = trav(incd[2][X[node] - Y[node]], node, X[node] + dist[pd], 2);
				if(nxt.fi != -1 && dist[nxt.fi] > nxt.se){
					dist[nxt.fi] = nxt.se; pq.push({dist[nxt.fi], nxt.fi});
				}

			}

			colored[node] = true;
			cnt++;
		}
	}

	return cnt;
}

void rotate(){
	for(ll i = 0; i < N; i++){
		swap(X[i], Y[i]);
		Y[i] = -Y[i];
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N;
	for(ll i = 0; i < N; i++){
		cin >> X[i] >> Y[i]; X[i] <<= 1, Y[i] <<= 1;
		if(i != 0) X[i] -= X[0], Y[i] -= Y[0];
	}
	X[0] = Y[0] = 0;

	ll ans = 0;
	for(ll i = 0; i < 4; i++){
		ans = max(ans, solve());
		rotate();
	}

	cout << ans << '\n';
}

Compilation message

fever.cpp: In function 'void buildEdge(std::vector<std::pair<long long int, long long int> >&, long long int, long long int)':
fever.cpp:25:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for(ll i = 1; i < v.size(); i++){
      |                 ~~^~~~~~~~~~
fever.cpp: In function 'std::pair<long long int, long long int> trav(std::vector<std::pair<long long int, long long int> >&, long long int, long long int, long long int)':
fever.cpp:43:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  if(idx == v.size()) return make_pair(-1, 0);
      |     ~~~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	29808 KB	Output is correct
2	Correct	27 ms	29652 KB	Output is correct
3	Correct	22 ms	29652 KB	Output is correct
4	Correct	26 ms	29628 KB	Output is correct
5	Correct	22 ms	29708 KB	Output is correct
6	Correct	23 ms	29672 KB	Output is correct
7	Correct	24 ms	29596 KB	Output is correct
8	Correct	22 ms	29652 KB	Output is correct
9	Correct	26 ms	29688 KB	Output is correct
10	Correct	24 ms	29608 KB	Output is correct
11	Correct	26 ms	29620 KB	Output is correct
12	Correct	24 ms	29672 KB	Output is correct
13	Correct	26 ms	29652 KB	Output is correct
14	Correct	23 ms	29672 KB	Output is correct
15	Correct	22 ms	29716 KB	Output is correct
16	Correct	23 ms	29672 KB	Output is correct
17	Correct	24 ms	29672 KB	Output is correct
18	Correct	24 ms	29672 KB	Output is correct
19	Correct	28 ms	29708 KB	Output is correct
20	Correct	26 ms	29700 KB	Output is correct
21	Correct	23 ms	29644 KB	Output is correct
22	Correct	23 ms	29660 KB	Output is correct
23	Correct	21 ms	29712 KB	Output is correct
24	Correct	22 ms	29672 KB	Output is correct
25	Correct	22 ms	29652 KB	Output is correct
26	Correct	23 ms	29668 KB	Output is correct
27	Correct	26 ms	29652 KB	Output is correct
28	Correct	25 ms	29660 KB	Output is correct
29	Correct	24 ms	29652 KB	Output is correct
30	Correct	25 ms	29652 KB	Output is correct
31	Correct	23 ms	29676 KB	Output is correct
32	Correct	24 ms	29652 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	29808 KB	Output is correct
2	Correct	27 ms	29652 KB	Output is correct
3	Correct	22 ms	29652 KB	Output is correct
4	Correct	26 ms	29628 KB	Output is correct
5	Correct	22 ms	29708 KB	Output is correct
6	Correct	23 ms	29672 KB	Output is correct
7	Correct	24 ms	29596 KB	Output is correct
8	Correct	22 ms	29652 KB	Output is correct
9	Correct	26 ms	29688 KB	Output is correct
10	Correct	24 ms	29608 KB	Output is correct
11	Correct	26 ms	29620 KB	Output is correct
12	Correct	24 ms	29672 KB	Output is correct
13	Correct	26 ms	29652 KB	Output is correct
14	Correct	23 ms	29672 KB	Output is correct
15	Correct	22 ms	29716 KB	Output is correct
16	Correct	23 ms	29672 KB	Output is correct
17	Correct	24 ms	29672 KB	Output is correct
18	Correct	24 ms	29672 KB	Output is correct
19	Correct	28 ms	29708 KB	Output is correct
20	Correct	26 ms	29700 KB	Output is correct
21	Correct	23 ms	29644 KB	Output is correct
22	Correct	23 ms	29660 KB	Output is correct
23	Correct	21 ms	29712 KB	Output is correct
24	Correct	22 ms	29672 KB	Output is correct
25	Correct	22 ms	29652 KB	Output is correct
26	Correct	23 ms	29668 KB	Output is correct
27	Correct	26 ms	29652 KB	Output is correct
28	Correct	25 ms	29660 KB	Output is correct
29	Correct	24 ms	29652 KB	Output is correct
30	Correct	25 ms	29652 KB	Output is correct
31	Correct	23 ms	29676 KB	Output is correct
32	Correct	24 ms	29652 KB	Output is correct
33	Correct	26 ms	29652 KB	Output is correct
34	Correct	23 ms	29676 KB	Output is correct
35	Correct	27 ms	29612 KB	Output is correct
36	Correct	24 ms	29724 KB	Output is correct
37	Correct	22 ms	29672 KB	Output is correct
38	Correct	30 ms	29712 KB	Output is correct
39	Correct	25 ms	29672 KB	Output is correct
40	Correct	24 ms	29652 KB	Output is correct
41	Correct	24 ms	29724 KB	Output is correct
42	Correct	25 ms	29672 KB	Output is correct
43	Correct	25 ms	29692 KB	Output is correct
44	Correct	24 ms	29652 KB	Output is correct
45	Correct	23 ms	29652 KB	Output is correct

Subtask #3
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	29652 KB	Output is correct
2	Correct	24 ms	29652 KB	Output is correct
3	Correct	23 ms	29736 KB	Output is correct
4	Correct	24 ms	29652 KB	Output is correct
5	Correct	25 ms	29672 KB	Output is correct
6	Correct	23 ms	29764 KB	Output is correct
7	Correct	22 ms	29716 KB	Output is correct
8	Correct	23 ms	29760 KB	Output is correct

Subtask #4
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	29808 KB	Output is correct
2	Correct	27 ms	29652 KB	Output is correct
3	Correct	22 ms	29652 KB	Output is correct
4	Correct	26 ms	29628 KB	Output is correct
5	Correct	22 ms	29708 KB	Output is correct
6	Correct	23 ms	29672 KB	Output is correct
7	Correct	24 ms	29596 KB	Output is correct
8	Correct	22 ms	29652 KB	Output is correct
9	Correct	26 ms	29688 KB	Output is correct
10	Correct	24 ms	29608 KB	Output is correct
11	Correct	26 ms	29620 KB	Output is correct
12	Correct	24 ms	29672 KB	Output is correct
13	Correct	26 ms	29652 KB	Output is correct
14	Correct	23 ms	29672 KB	Output is correct
15	Correct	22 ms	29716 KB	Output is correct
16	Correct	23 ms	29672 KB	Output is correct
17	Correct	24 ms	29672 KB	Output is correct
18	Correct	24 ms	29672 KB	Output is correct
19	Correct	28 ms	29708 KB	Output is correct
20	Correct	26 ms	29700 KB	Output is correct
21	Correct	23 ms	29644 KB	Output is correct
22	Correct	23 ms	29660 KB	Output is correct
23	Correct	21 ms	29712 KB	Output is correct
24	Correct	22 ms	29672 KB	Output is correct
25	Correct	22 ms	29652 KB	Output is correct
26	Correct	23 ms	29668 KB	Output is correct
27	Correct	26 ms	29652 KB	Output is correct
28	Correct	25 ms	29660 KB	Output is correct
29	Correct	24 ms	29652 KB	Output is correct
30	Correct	25 ms	29652 KB	Output is correct
31	Correct	23 ms	29676 KB	Output is correct
32	Correct	24 ms	29652 KB	Output is correct
33	Correct	26 ms	29652 KB	Output is correct
34	Correct	23 ms	29676 KB	Output is correct
35	Correct	27 ms	29612 KB	Output is correct
36	Correct	24 ms	29724 KB	Output is correct
37	Correct	22 ms	29672 KB	Output is correct
38	Correct	30 ms	29712 KB	Output is correct
39	Correct	25 ms	29672 KB	Output is correct
40	Correct	24 ms	29652 KB	Output is correct
41	Correct	24 ms	29724 KB	Output is correct
42	Correct	25 ms	29672 KB	Output is correct
43	Correct	25 ms	29692 KB	Output is correct
44	Correct	24 ms	29652 KB	Output is correct
45	Correct	23 ms	29652 KB	Output is correct
46	Correct	27 ms	29652 KB	Output is correct
47	Correct	24 ms	29652 KB	Output is correct
48	Correct	23 ms	29736 KB	Output is correct
49	Correct	24 ms	29652 KB	Output is correct
50	Correct	25 ms	29672 KB	Output is correct
51	Correct	23 ms	29764 KB	Output is correct
52	Correct	22 ms	29716 KB	Output is correct
53	Correct	23 ms	29760 KB	Output is correct
54	Correct	28 ms	29652 KB	Output is correct
55	Correct	27 ms	29668 KB	Output is correct
56	Correct	24 ms	29644 KB	Output is correct
57	Correct	23 ms	29652 KB	Output is correct
58	Correct	23 ms	29652 KB	Output is correct
59	Correct	25 ms	29740 KB	Output is correct
60	Correct	23 ms	29704 KB	Output is correct
61	Correct	25 ms	29652 KB	Output is correct
62	Correct	26 ms	29672 KB	Output is correct
63	Correct	24 ms	29736 KB	Output is correct
64	Correct	28 ms	29652 KB	Output is correct
65	Correct	25 ms	29728 KB	Output is correct

Subtask #5
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	29808 KB	Output is correct
2	Correct	27 ms	29652 KB	Output is correct
3	Correct	22 ms	29652 KB	Output is correct
4	Correct	26 ms	29628 KB	Output is correct
5	Correct	22 ms	29708 KB	Output is correct
6	Correct	23 ms	29672 KB	Output is correct
7	Correct	24 ms	29596 KB	Output is correct
8	Correct	22 ms	29652 KB	Output is correct
9	Correct	26 ms	29688 KB	Output is correct
10	Correct	24 ms	29608 KB	Output is correct
11	Correct	26 ms	29620 KB	Output is correct
12	Correct	24 ms	29672 KB	Output is correct
13	Correct	26 ms	29652 KB	Output is correct
14	Correct	23 ms	29672 KB	Output is correct
15	Correct	22 ms	29716 KB	Output is correct
16	Correct	23 ms	29672 KB	Output is correct
17	Correct	24 ms	29672 KB	Output is correct
18	Correct	24 ms	29672 KB	Output is correct
19	Correct	28 ms	29708 KB	Output is correct
20	Correct	26 ms	29700 KB	Output is correct
21	Correct	23 ms	29644 KB	Output is correct
22	Correct	23 ms	29660 KB	Output is correct
23	Correct	21 ms	29712 KB	Output is correct
24	Correct	22 ms	29672 KB	Output is correct
25	Correct	22 ms	29652 KB	Output is correct
26	Correct	23 ms	29668 KB	Output is correct
27	Correct	26 ms	29652 KB	Output is correct
28	Correct	25 ms	29660 KB	Output is correct
29	Correct	24 ms	29652 KB	Output is correct
30	Correct	25 ms	29652 KB	Output is correct
31	Correct	23 ms	29676 KB	Output is correct
32	Correct	24 ms	29652 KB	Output is correct
33	Correct	26 ms	29652 KB	Output is correct
34	Correct	23 ms	29676 KB	Output is correct
35	Correct	27 ms	29612 KB	Output is correct
36	Correct	24 ms	29724 KB	Output is correct
37	Correct	22 ms	29672 KB	Output is correct
38	Correct	30 ms	29712 KB	Output is correct
39	Correct	25 ms	29672 KB	Output is correct
40	Correct	24 ms	29652 KB	Output is correct
41	Correct	24 ms	29724 KB	Output is correct
42	Correct	25 ms	29672 KB	Output is correct
43	Correct	25 ms	29692 KB	Output is correct
44	Correct	24 ms	29652 KB	Output is correct
45	Correct	23 ms	29652 KB	Output is correct
46	Correct	27 ms	29652 KB	Output is correct
47	Correct	24 ms	29652 KB	Output is correct
48	Correct	23 ms	29736 KB	Output is correct
49	Correct	24 ms	29652 KB	Output is correct
50	Correct	25 ms	29672 KB	Output is correct
51	Correct	23 ms	29764 KB	Output is correct
52	Correct	22 ms	29716 KB	Output is correct
53	Correct	23 ms	29760 KB	Output is correct
54	Correct	28 ms	29652 KB	Output is correct
55	Correct	27 ms	29668 KB	Output is correct
56	Correct	24 ms	29644 KB	Output is correct
57	Correct	23 ms	29652 KB	Output is correct
58	Correct	23 ms	29652 KB	Output is correct
59	Correct	25 ms	29740 KB	Output is correct
60	Correct	23 ms	29704 KB	Output is correct
61	Correct	25 ms	29652 KB	Output is correct
62	Correct	26 ms	29672 KB	Output is correct
63	Correct	24 ms	29736 KB	Output is correct
64	Correct	28 ms	29652 KB	Output is correct
65	Correct	25 ms	29728 KB	Output is correct
66	Correct	39 ms	30960 KB	Output is correct
67	Correct	40 ms	30932 KB	Output is correct
68	Correct	46 ms	31132 KB	Output is correct
69	Correct	39 ms	30444 KB	Output is correct
70	Correct	43 ms	30524 KB	Output is correct
71	Correct	40 ms	30704 KB	Output is correct
72	Correct	39 ms	30948 KB	Output is correct
73	Correct	43 ms	31060 KB	Output is correct
74	Correct	39 ms	31468 KB	Output is correct
75	Correct	44 ms	31456 KB	Output is correct
76	Correct	45 ms	31060 KB	Output is correct
77	Correct	40 ms	30964 KB	Output is correct
78	Correct	44 ms	31192 KB	Output is correct
79	Correct	42 ms	31280 KB	Output is correct
80	Correct	40 ms	31052 KB	Output is correct
81	Correct	44 ms	31232 KB	Output is correct
82	Correct	41 ms	31412 KB	Output is correct
83	Correct	43 ms	31424 KB	Output is correct
84	Correct	31 ms	30808 KB	Output is correct
85	Correct	29 ms	30452 KB	Output is correct
86	Correct	29 ms	30396 KB	Output is correct
87	Correct	29 ms	30548 KB	Output is correct
88	Correct	44 ms	31512 KB	Output is correct
89	Correct	42 ms	31340 KB	Output is correct
90	Correct	42 ms	31340 KB	Output is correct

Subtask #6
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	29808 KB	Output is correct
2	Correct	27 ms	29652 KB	Output is correct
3	Correct	22 ms	29652 KB	Output is correct
4	Correct	26 ms	29628 KB	Output is correct
5	Correct	22 ms	29708 KB	Output is correct
6	Correct	23 ms	29672 KB	Output is correct
7	Correct	24 ms	29596 KB	Output is correct
8	Correct	22 ms	29652 KB	Output is correct
9	Correct	26 ms	29688 KB	Output is correct
10	Correct	24 ms	29608 KB	Output is correct
11	Correct	26 ms	29620 KB	Output is correct
12	Correct	24 ms	29672 KB	Output is correct
13	Correct	26 ms	29652 KB	Output is correct
14	Correct	23 ms	29672 KB	Output is correct
15	Correct	22 ms	29716 KB	Output is correct
16	Correct	23 ms	29672 KB	Output is correct
17	Correct	24 ms	29672 KB	Output is correct
18	Correct	24 ms	29672 KB	Output is correct
19	Correct	28 ms	29708 KB	Output is correct
20	Correct	26 ms	29700 KB	Output is correct
21	Correct	23 ms	29644 KB	Output is correct
22	Correct	23 ms	29660 KB	Output is correct
23	Correct	21 ms	29712 KB	Output is correct
24	Correct	22 ms	29672 KB	Output is correct
25	Correct	22 ms	29652 KB	Output is correct
26	Correct	23 ms	29668 KB	Output is correct
27	Correct	26 ms	29652 KB	Output is correct
28	Correct	25 ms	29660 KB	Output is correct
29	Correct	24 ms	29652 KB	Output is correct
30	Correct	25 ms	29652 KB	Output is correct
31	Correct	23 ms	29676 KB	Output is correct
32	Correct	24 ms	29652 KB	Output is correct
33	Correct	26 ms	29652 KB	Output is correct
34	Correct	23 ms	29676 KB	Output is correct
35	Correct	27 ms	29612 KB	Output is correct
36	Correct	24 ms	29724 KB	Output is correct
37	Correct	22 ms	29672 KB	Output is correct
38	Correct	30 ms	29712 KB	Output is correct
39	Correct	25 ms	29672 KB	Output is correct
40	Correct	24 ms	29652 KB	Output is correct
41	Correct	24 ms	29724 KB	Output is correct
42	Correct	25 ms	29672 KB	Output is correct
43	Correct	25 ms	29692 KB	Output is correct
44	Correct	24 ms	29652 KB	Output is correct
45	Correct	23 ms	29652 KB	Output is correct
46	Correct	27 ms	29652 KB	Output is correct
47	Correct	24 ms	29652 KB	Output is correct
48	Correct	23 ms	29736 KB	Output is correct
49	Correct	24 ms	29652 KB	Output is correct
50	Correct	25 ms	29672 KB	Output is correct
51	Correct	23 ms	29764 KB	Output is correct
52	Correct	22 ms	29716 KB	Output is correct
53	Correct	23 ms	29760 KB	Output is correct
54	Correct	28 ms	29652 KB	Output is correct
55	Correct	27 ms	29668 KB	Output is correct
56	Correct	24 ms	29644 KB	Output is correct
57	Correct	23 ms	29652 KB	Output is correct
58	Correct	23 ms	29652 KB	Output is correct
59	Correct	25 ms	29740 KB	Output is correct
60	Correct	23 ms	29704 KB	Output is correct
61	Correct	25 ms	29652 KB	Output is correct
62	Correct	26 ms	29672 KB	Output is correct
63	Correct	24 ms	29736 KB	Output is correct
64	Correct	28 ms	29652 KB	Output is correct
65	Correct	25 ms	29728 KB	Output is correct
66	Correct	1720 ms	66120 KB	Output is correct
67	Correct	2142 ms	74708 KB	Output is correct
68	Correct	2267 ms	77784 KB	Output is correct
69	Correct	1347 ms	90140 KB	Output is correct
70	Correct	1479 ms	90860 KB	Output is correct
71	Correct	2197 ms	77804 KB	Output is correct
72	Correct	2337 ms	77540 KB	Output is correct
73	Correct	1832 ms	73524 KB	Output is correct
74	Correct	2360 ms	77848 KB	Output is correct
75	Correct	2221 ms	78584 KB	Output is correct
76	Correct	1665 ms	87976 KB	Output is correct
77	Correct	2064 ms	77900 KB	Output is correct
78	Correct	2216 ms	85760 KB	Output is correct
79	Correct	2297 ms	85644 KB	Output is correct

Subtask #7
0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	29808 KB	Output is correct
2	Correct	27 ms	29652 KB	Output is correct
3	Correct	22 ms	29652 KB	Output is correct
4	Correct	26 ms	29628 KB	Output is correct
5	Correct	22 ms	29708 KB	Output is correct
6	Correct	23 ms	29672 KB	Output is correct
7	Correct	24 ms	29596 KB	Output is correct
8	Correct	22 ms	29652 KB	Output is correct
9	Correct	26 ms	29688 KB	Output is correct
10	Correct	24 ms	29608 KB	Output is correct
11	Correct	26 ms	29620 KB	Output is correct
12	Correct	24 ms	29672 KB	Output is correct
13	Correct	26 ms	29652 KB	Output is correct
14	Correct	23 ms	29672 KB	Output is correct
15	Correct	22 ms	29716 KB	Output is correct
16	Correct	23 ms	29672 KB	Output is correct
17	Correct	24 ms	29672 KB	Output is correct
18	Correct	24 ms	29672 KB	Output is correct
19	Correct	28 ms	29708 KB	Output is correct
20	Correct	26 ms	29700 KB	Output is correct
21	Correct	23 ms	29644 KB	Output is correct
22	Correct	23 ms	29660 KB	Output is correct
23	Correct	21 ms	29712 KB	Output is correct
24	Correct	22 ms	29672 KB	Output is correct
25	Correct	22 ms	29652 KB	Output is correct
26	Correct	23 ms	29668 KB	Output is correct
27	Correct	26 ms	29652 KB	Output is correct
28	Correct	25 ms	29660 KB	Output is correct
29	Correct	24 ms	29652 KB	Output is correct
30	Correct	25 ms	29652 KB	Output is correct
31	Correct	23 ms	29676 KB	Output is correct
32	Correct	24 ms	29652 KB	Output is correct
33	Correct	26 ms	29652 KB	Output is correct
34	Correct	23 ms	29676 KB	Output is correct
35	Correct	27 ms	29612 KB	Output is correct
36	Correct	24 ms	29724 KB	Output is correct
37	Correct	22 ms	29672 KB	Output is correct
38	Correct	30 ms	29712 KB	Output is correct
39	Correct	25 ms	29672 KB	Output is correct
40	Correct	24 ms	29652 KB	Output is correct
41	Correct	24 ms	29724 KB	Output is correct
42	Correct	25 ms	29672 KB	Output is correct
43	Correct	25 ms	29692 KB	Output is correct
44	Correct	24 ms	29652 KB	Output is correct
45	Correct	23 ms	29652 KB	Output is correct
46	Correct	27 ms	29652 KB	Output is correct
47	Correct	24 ms	29652 KB	Output is correct
48	Correct	23 ms	29736 KB	Output is correct
49	Correct	24 ms	29652 KB	Output is correct
50	Correct	25 ms	29672 KB	Output is correct
51	Correct	23 ms	29764 KB	Output is correct
52	Correct	22 ms	29716 KB	Output is correct
53	Correct	23 ms	29760 KB	Output is correct
54	Correct	28 ms	29652 KB	Output is correct
55	Correct	27 ms	29668 KB	Output is correct
56	Correct	24 ms	29644 KB	Output is correct
57	Correct	23 ms	29652 KB	Output is correct
58	Correct	23 ms	29652 KB	Output is correct
59	Correct	25 ms	29740 KB	Output is correct
60	Correct	23 ms	29704 KB	Output is correct
61	Correct	25 ms	29652 KB	Output is correct
62	Correct	26 ms	29672 KB	Output is correct
63	Correct	24 ms	29736 KB	Output is correct
64	Correct	28 ms	29652 KB	Output is correct
65	Correct	25 ms	29728 KB	Output is correct
66	Correct	39 ms	30960 KB	Output is correct
67	Correct	40 ms	30932 KB	Output is correct
68	Correct	46 ms	31132 KB	Output is correct
69	Correct	39 ms	30444 KB	Output is correct
70	Correct	43 ms	30524 KB	Output is correct
71	Correct	40 ms	30704 KB	Output is correct
72	Correct	39 ms	30948 KB	Output is correct
73	Correct	43 ms	31060 KB	Output is correct
74	Correct	39 ms	31468 KB	Output is correct
75	Correct	44 ms	31456 KB	Output is correct
76	Correct	45 ms	31060 KB	Output is correct
77	Correct	40 ms	30964 KB	Output is correct
78	Correct	44 ms	31192 KB	Output is correct
79	Correct	42 ms	31280 KB	Output is correct
80	Correct	40 ms	31052 KB	Output is correct
81	Correct	44 ms	31232 KB	Output is correct
82	Correct	41 ms	31412 KB	Output is correct
83	Correct	43 ms	31424 KB	Output is correct
84	Correct	31 ms	30808 KB	Output is correct
85	Correct	29 ms	30452 KB	Output is correct
86	Correct	29 ms	30396 KB	Output is correct
87	Correct	29 ms	30548 KB	Output is correct
88	Correct	44 ms	31512 KB	Output is correct
89	Correct	42 ms	31340 KB	Output is correct
90	Correct	42 ms	31340 KB	Output is correct
91	Correct	1720 ms	66120 KB	Output is correct
92	Correct	2142 ms	74708 KB	Output is correct
93	Correct	2267 ms	77784 KB	Output is correct
94	Correct	1347 ms	90140 KB	Output is correct
95	Correct	1479 ms	90860 KB	Output is correct
96	Correct	2197 ms	77804 KB	Output is correct
97	Correct	2337 ms	77540 KB	Output is correct
98	Correct	1832 ms	73524 KB	Output is correct
99	Correct	2360 ms	77848 KB	Output is correct
100	Correct	2221 ms	78584 KB	Output is correct
101	Correct	1665 ms	87976 KB	Output is correct
102	Correct	2064 ms	77900 KB	Output is correct
103	Correct	2216 ms	85760 KB	Output is correct
104	Correct	2297 ms	85644 KB	Output is correct
105	Correct	585 ms	48204 KB	Output is correct
106	Correct	724 ms	52756 KB	Output is correct
107	Correct	1051 ms	53880 KB	Output is correct
108	Incorrect	941 ms	53848 KB	Output isn't correct
109	Halted	0 ms	0 KB	-

답안 #579030

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 8.0 / 8.0

Subtask #3 6.0 / 6.0

Subtask #4 6.0 / 6.0

Subtask #5 12.0 / 12.0

Subtask #6 32.0 / 32.0

Subtask #7 0 / 31.0

Subtask #1
5.0 / 5.0

Subtask #2
8.0 / 8.0

Subtask #3
6.0 / 6.0

Subtask #4
6.0 / 6.0

Subtask #5
12.0 / 12.0

Subtask #6
32.0 / 32.0

Subtask #7
0 / 31.0