oj.uz

Submission #924176

# Submission time Handle Problem Language Result Execution time Memory
924176 2024-02-08T15:52:34 Z Edu175 Maze (JOI23_ho_t3) C++17
86 / 100
 2000 ms 892780 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ggdem=b;i<ggdem;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define imp(v) for(auto edu:v)cout<<edu<<" "; cout<<"\n"
using namespace std;
typedef int ll;
typedef pair<ll,ll> ii;
#pragma GCC optimize("Ofast") // may lead to precision errors

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const ll MAXN=6e6+5;

ll a[MAXN];
ll n,m,k;
inline ll cv(ii x){return m*x.fst+x.snd;}
inline ii cv(ll x){return {x/m,x%m};}
vector<ll>dir;
//vector<ii>diir={{0,1},{-1,0},{0,-1},{1,0}};
//ii operator+(ii a, ii b){return {a.fst+b.fst,a.snd+b.snd};}
//void operator+=(ii &a, ii b){a=a+b;}
bool allowed(ll x, ll w){
	auto [i,j]=cv(x);
	if(w==0&&j>=m-1)return 0;
	if(w==1&&i<=0)return 0;
	if(w==2&&j<=0)return 0;
	if(w==3&&i>=n-1)return 0;
	return 1;
}
ll d[MAXN],vis[MAXN];
deque<pair<ll,bool>>q;
set<ll>r[MAXN],c[MAXN];
vector<ll>pop;
void go(ll x, ll y, ll g){
	if(vis[y])return;
	d[y]=d[x]+g;
	q.push_front({y,0});
	vis[y]=1;
	pop.pb(y);
}
void popit(){
	for(auto x:pop){
		auto [i,j]=cv(x);
		r[i].erase(j);
		c[j].erase(i);
	}
	pop.clear();
}
ll reach(ll _x, ll _e){
	ii x=cv(_x),e=cv(_e);
	return (max(abs(x.fst-e.fst),abs(x.snd-e.snd))<=k&&
	       abs(x.fst-e.fst)+abs(x.snd-e.snd)<2*k);
}

ll bfs(ll s, ll e){
	mset(d,-1);
	d[s]=0;
	q.push_front({s,0});
	while(SZ(q)){
		auto [x,g]=q.front(); q.pop_front();
		if(!g){
			fore(w,0,4){
				auto y=x+dir[w];
				if(!allowed(x,w)||(!g&&a[y]))continue;
				go(x,y,0);
				popit();
			}
			q.pb({x,1});
		}
		else {
			auto [i,j]=cv(x);
			if(reach(x,e))go(x,e,1);
			if(i-k>=0)
				for(auto it=r[i-k].upper_bound(j-k);
				it!=r[i-k].end()&&*it<j+k;it++)go(x,cv({i-k,*it}),1);
			if(i+k<n)
				for(auto it=r[i+k].upper_bound(j-k);
				it!=r[i+k].end()&&*it<j+k;it++)go(x,cv({i+k,*it}),1);
			if(j-k>=0)
				for(auto it=c[j-k].upper_bound(i-k);
				it!=c[j-k].end()&&*it<i+k;it++)go(x,cv({*it,j-k}),1);
			if(j+k<m)
				for(auto it=c[j+k].upper_bound(i-k);
				it!=c[j+k].end()&&*it<i+k;it++)go(x,cv({*it,j+k}),1);
			popit();
		}
	}
	return d[e];
}

int main(){FIN;
	cin>>n>>m>>k;
	dir={1,-m,-1,m};
	ii s,e; cin>>s.fst>>s.snd>>e.fst>>e.snd; s.fst--,s.snd--,e.fst--,e.snd--;
	fore(i,0,n*m){
		char c; cin>>c;
		a[i]=(c=='#');
	}
	fore(i,0,n)fore(j,0,m)r[i].insert(j),c[j].insert(i);
	cout<<bfs(cv(s),cv(e))<<"\n";
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 589348 KB Output is correct
2 Correct 193 ms 589396 KB Output is correct
3 Correct 194 ms 589572 KB Output is correct
4 Correct 192 ms 589368 KB Output is correct
5 Correct 135 ms 589356 KB Output is correct
6 Correct 249 ms 588624 KB Output is correct
7 Correct 237 ms 587636 KB Output is correct
8 Correct 147 ms 588484 KB Output is correct
9 Correct 243 ms 587344 KB Output is correct
10 Correct 233 ms 587536 KB Output is correct
11 Correct 194 ms 587528 KB Output is correct
12 Correct 239 ms 587344 KB Output is correct
13 Correct 245 ms 587348 KB Output is correct
14 Correct 245 ms 587504 KB Output is correct
15 Correct 193 ms 589396 KB Output is correct
16 Correct 182 ms 589592 KB Output is correct
17 Correct 142 ms 589392 KB Output is correct
18 Correct 190 ms 589420 KB Output is correct
19 Correct 251 ms 595024 KB Output is correct
20 Correct 179 ms 594108 KB Output is correct
21 Correct 207 ms 595032 KB Output is correct
22 Correct 209 ms 595136 KB Output is correct
23 Correct 217 ms 595120 KB Output is correct
24 Correct 197 ms 595068 KB Output is correct
25 Correct 173 ms 595044 KB Output is correct
26 Correct 205 ms 595024 KB Output is correct
27 Correct 205 ms 595072 KB Output is correct
28 Correct 202 ms 595128 KB Output is correct
29 Correct 245 ms 603544 KB Output is correct
30 Correct 222 ms 595084 KB Output is correct
31 Correct 246 ms 603628 KB Output is correct
32 Correct 269 ms 603588 KB Output is correct
33 Correct 255 ms 603476 KB Output is correct
34 Correct 242 ms 603584 KB Output is correct
35 Correct 185 ms 602600 KB Output is correct
36 Correct 247 ms 603584 KB Output is correct
37 Correct 283 ms 603732 KB Output is correct
38 Correct 215 ms 602828 KB Output is correct
39 Correct 1109 ms 739932 KB Output is correct
40 Correct 276 ms 605440 KB Output is correct
41 Correct 250 ms 606652 KB Output is correct
42 Correct 258 ms 609364 KB Output is correct
43 Correct 239 ms 612280 KB Output is correct
44 Correct 602 ms 662908 KB Output is correct
45 Correct 576 ms 668980 KB Output is correct
46 Correct 1048 ms 740568 KB Output is correct
47 Correct 1067 ms 740176 KB Output is correct
48 Correct 1202 ms 740292 KB Output is correct
49 Correct 761 ms 740048 KB Output is correct
50 Correct 766 ms 739984 KB Output is correct
51 Correct 1221 ms 739988 KB Output is correct
52 Correct 1338 ms 740216 KB Output is correct
53 Correct 1349 ms 740144 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 589464 KB Output is correct
2 Correct 158 ms 589424 KB Output is correct
3 Correct 199 ms 589504 KB Output is correct
4 Correct 199 ms 589276 KB Output is correct
5 Correct 200 ms 589536 KB Output is correct
6 Correct 198 ms 589496 KB Output is correct
7 Correct 196 ms 589396 KB Output is correct
8 Correct 195 ms 589376 KB Output is correct
9 Correct 203 ms 589396 KB Output is correct
10 Correct 192 ms 589396 KB Output is correct
11 Correct 200 ms 589396 KB Output is correct
12 Correct 215 ms 589492 KB Output is correct
13 Correct 198 ms 589396 KB Output is correct
14 Correct 213 ms 589360 KB Output is correct
15 Correct 190 ms 589556 KB Output is correct
16 Correct 192 ms 589384 KB Output is correct
17 Correct 214 ms 589516 KB Output is correct
18 Correct 140 ms 589400 KB Output is correct
19 Correct 179 ms 587604 KB Output is correct
20 Correct 176 ms 587344 KB Output is correct
21 Correct 139 ms 587344 KB Output is correct
22 Correct 242 ms 589616 KB Output is correct
23 Correct 193 ms 589336 KB Output is correct
24 Correct 188 ms 589396 KB Output is correct
25 Correct 188 ms 589392 KB Output is correct
26 Correct 192 ms 589428 KB Output is correct
27 Correct 193 ms 589356 KB Output is correct
28 Correct 190 ms 589392 KB Output is correct
29 Correct 184 ms 589500 KB Output is correct
30 Correct 135 ms 589392 KB Output is correct
31 Correct 241 ms 588936 KB Output is correct
32 Correct 248 ms 588628 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 588628 KB Output is correct
2 Correct 195 ms 589376 KB Output is correct
3 Correct 191 ms 589500 KB Output is correct
4 Correct 174 ms 589396 KB Output is correct
5 Correct 197 ms 589360 KB Output is correct
6 Correct 188 ms 589288 KB Output is correct
7 Correct 182 ms 589508 KB Output is correct
8 Correct 189 ms 589392 KB Output is correct
9 Correct 182 ms 589392 KB Output is correct
10 Correct 186 ms 589588 KB Output is correct
11 Correct 185 ms 589344 KB Output is correct
12 Correct 182 ms 589396 KB Output is correct
13 Correct 177 ms 589384 KB Output is correct
14 Correct 175 ms 589396 KB Output is correct
15 Correct 179 ms 589500 KB Output is correct
16 Correct 198 ms 589800 KB Output is correct
17 Correct 137 ms 587344 KB Output is correct
18 Correct 151 ms 587508 KB Output is correct
19 Correct 141 ms 587408 KB Output is correct
20 Correct 168 ms 587348 KB Output is correct
21 Correct 211 ms 589608 KB Output is correct
22 Correct 194 ms 589436 KB Output is correct
23 Correct 206 ms 589636 KB Output is correct
24 Correct 203 ms 589652 KB Output is correct
25 Correct 207 ms 592980 KB Output is correct
26 Correct 249 ms 594596 KB Output is correct
27 Correct 225 ms 595084 KB Output is correct
28 Correct 213 ms 595024 KB Output is correct
29 Correct 224 ms 595116 KB Output is correct
30 Correct 239 ms 595116 KB Output is correct
31 Correct 262 ms 594944 KB Output is correct
32 Correct 264 ms 595068 KB Output is correct
33 Correct 165 ms 593596 KB Output is correct
34 Correct 192 ms 600820 KB Output is correct
35 Correct 201 ms 603472 KB Output is correct
36 Correct 223 ms 603404 KB Output is correct
37 Correct 223 ms 603608 KB Output is correct
38 Correct 229 ms 602140 KB Output is correct
39 Correct 495 ms 632112 KB Output is correct
40 Correct 1125 ms 717928 KB Output is correct
41 Correct 1258 ms 742000 KB Output is correct
42 Correct 1104 ms 742252 KB Output is correct
43 Correct 821 ms 738128 KB Output is correct
44 Correct 757 ms 736456 KB Output is correct
45 Correct 1312 ms 742052 KB Output is correct
46 Correct 1377 ms 743340 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 589464 KB Output is correct
2 Correct 158 ms 589424 KB Output is correct
3 Correct 199 ms 589504 KB Output is correct
4 Correct 199 ms 589276 KB Output is correct
5 Correct 200 ms 589536 KB Output is correct
6 Correct 198 ms 589496 KB Output is correct
7 Correct 196 ms 589396 KB Output is correct
8 Correct 195 ms 589376 KB Output is correct
9 Correct 203 ms 589396 KB Output is correct
10 Correct 192 ms 589396 KB Output is correct
11 Correct 200 ms 589396 KB Output is correct
12 Correct 215 ms 589492 KB Output is correct
13 Correct 198 ms 589396 KB Output is correct
14 Correct 213 ms 589360 KB Output is correct
15 Correct 190 ms 589556 KB Output is correct
16 Correct 192 ms 589384 KB Output is correct
17 Correct 214 ms 589516 KB Output is correct
18 Correct 140 ms 589400 KB Output is correct
19 Correct 179 ms 587604 KB Output is correct
20 Correct 176 ms 587344 KB Output is correct
21 Correct 139 ms 587344 KB Output is correct
22 Correct 242 ms 589616 KB Output is correct
23 Correct 193 ms 589336 KB Output is correct
24 Correct 188 ms 589396 KB Output is correct
25 Correct 188 ms 589392 KB Output is correct
26 Correct 192 ms 589428 KB Output is correct
27 Correct 193 ms 589356 KB Output is correct
28 Correct 190 ms 589392 KB Output is correct
29 Correct 184 ms 589500 KB Output is correct
30 Correct 135 ms 589392 KB Output is correct
31 Correct 241 ms 588936 KB Output is correct
32 Correct 248 ms 588628 KB Output is correct
33 Correct 283 ms 593492 KB Output is correct
34 Correct 135 ms 589648 KB Output is correct
35 Correct 227 ms 587860 KB Output is correct
36 Correct 262 ms 591444 KB Output is correct
37 Correct 233 ms 593744 KB Output is correct
38 Correct 247 ms 594620 KB Output is correct
39 Correct 206 ms 595020 KB Output is correct
40 Correct 181 ms 593556 KB Output is correct
41 Correct 238 ms 593680 KB Output is correct
42 Correct 265 ms 593492 KB Output is correct
43 Correct 287 ms 594992 KB Output is correct
44 Correct 254 ms 595364 KB Output is correct
45 Correct 220 ms 594424 KB Output is correct
46 Correct 307 ms 593708 KB Output is correct
47 Correct 246 ms 595196 KB Output is correct
48 Correct 254 ms 595196 KB Output is correct
49 Correct 270 ms 595212 KB Output is correct
50 Correct 238 ms 595020 KB Output is correct
51 Correct 249 ms 595204 KB Output is correct
52 Correct 246 ms 595028 KB Output is correct
53 Correct 281 ms 593480 KB Output is correct
54 Correct 291 ms 593748 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 589464 KB Output is correct
2 Correct 158 ms 589424 KB Output is correct
3 Correct 199 ms 589504 KB Output is correct
4 Correct 199 ms 589276 KB Output is correct
5 Correct 200 ms 589536 KB Output is correct
6 Correct 198 ms 589496 KB Output is correct
7 Correct 196 ms 589396 KB Output is correct
8 Correct 195 ms 589376 KB Output is correct
9 Correct 203 ms 589396 KB Output is correct
10 Correct 192 ms 589396 KB Output is correct
11 Correct 200 ms 589396 KB Output is correct
12 Correct 215 ms 589492 KB Output is correct
13 Correct 198 ms 589396 KB Output is correct
14 Correct 213 ms 589360 KB Output is correct
15 Correct 190 ms 589556 KB Output is correct
16 Correct 192 ms 589384 KB Output is correct
17 Correct 214 ms 589516 KB Output is correct
18 Correct 140 ms 589400 KB Output is correct
19 Correct 179 ms 587604 KB Output is correct
20 Correct 176 ms 587344 KB Output is correct
21 Correct 139 ms 587344 KB Output is correct
22 Correct 242 ms 589616 KB Output is correct
23 Correct 193 ms 589336 KB Output is correct
24 Correct 188 ms 589396 KB Output is correct
25 Correct 188 ms 589392 KB Output is correct
26 Correct 192 ms 589428 KB Output is correct
27 Correct 193 ms 589356 KB Output is correct
28 Correct 190 ms 589392 KB Output is correct
29 Correct 184 ms 589500 KB Output is correct
30 Correct 135 ms 589392 KB Output is correct
31 Correct 241 ms 588936 KB Output is correct
32 Correct 248 ms 588628 KB Output is correct
33 Correct 283 ms 593492 KB Output is correct
34 Correct 135 ms 589648 KB Output is correct
35 Correct 227 ms 587860 KB Output is correct
36 Correct 262 ms 591444 KB Output is correct
37 Correct 233 ms 593744 KB Output is correct
38 Correct 247 ms 594620 KB Output is correct
39 Correct 206 ms 595020 KB Output is correct
40 Correct 181 ms 593556 KB Output is correct
41 Correct 238 ms 593680 KB Output is correct
42 Correct 265 ms 593492 KB Output is correct
43 Correct 287 ms 594992 KB Output is correct
44 Correct 254 ms 595364 KB Output is correct
45 Correct 220 ms 594424 KB Output is correct
46 Correct 307 ms 593708 KB Output is correct
47 Correct 246 ms 595196 KB Output is correct
48 Correct 254 ms 595196 KB Output is correct
49 Correct 270 ms 595212 KB Output is correct
50 Correct 238 ms 595020 KB Output is correct
51 Correct 249 ms 595204 KB Output is correct
52 Correct 246 ms 595028 KB Output is correct
53 Correct 281 ms 593480 KB Output is correct
54 Correct 291 ms 593748 KB Output is correct
55 Correct 304 ms 603524 KB Output is correct
56 Correct 271 ms 593692 KB Output is correct
57 Correct 221 ms 599888 KB Output is correct
58 Correct 373 ms 601584 KB Output is correct
59 Correct 382 ms 602964 KB Output is correct
60 Correct 283 ms 603740 KB Output is correct
61 Correct 278 ms 603688 KB Output is correct
62 Correct 302 ms 603756 KB Output is correct
63 Correct 274 ms 603544 KB Output is correct
64 Correct 307 ms 603484 KB Output is correct
65 Correct 297 ms 603732 KB Output is correct
66 Correct 260 ms 603744 KB Output is correct
67 Correct 293 ms 603736 KB Output is correct
68 Correct 194 ms 603760 KB Output is correct
69 Correct 318 ms 603764 KB Output is correct
70 Correct 277 ms 603728 KB Output is correct
71 Correct 339 ms 602960 KB Output is correct
72 Correct 379 ms 602840 KB Output is correct
73 Correct 337 ms 602964 KB Output is correct
74 Correct 394 ms 603088 KB Output is correct

Subtask #6
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 589348 KB Output is correct
2 Correct 193 ms 589396 KB Output is correct
3 Correct 194 ms 589572 KB Output is correct
4 Correct 192 ms 589368 KB Output is correct
5 Correct 135 ms 589356 KB Output is correct
6 Correct 249 ms 588624 KB Output is correct
7 Correct 237 ms 587636 KB Output is correct
8 Correct 147 ms 588484 KB Output is correct
9 Correct 243 ms 587344 KB Output is correct
10 Correct 233 ms 587536 KB Output is correct
11 Correct 194 ms 587528 KB Output is correct
12 Correct 239 ms 587344 KB Output is correct
13 Correct 245 ms 587348 KB Output is correct
14 Correct 245 ms 587504 KB Output is correct
15 Correct 193 ms 589396 KB Output is correct
16 Correct 182 ms 589592 KB Output is correct
17 Correct 142 ms 589392 KB Output is correct
18 Correct 190 ms 589420 KB Output is correct
19 Correct 251 ms 595024 KB Output is correct
20 Correct 179 ms 594108 KB Output is correct
21 Correct 207 ms 595032 KB Output is correct
22 Correct 209 ms 595136 KB Output is correct
23 Correct 217 ms 595120 KB Output is correct
24 Correct 197 ms 595068 KB Output is correct
25 Correct 173 ms 595044 KB Output is correct
26 Correct 205 ms 595024 KB Output is correct
27 Correct 205 ms 595072 KB Output is correct
28 Correct 202 ms 595128 KB Output is correct
29 Correct 245 ms 603544 KB Output is correct
30 Correct 222 ms 595084 KB Output is correct
31 Correct 246 ms 603628 KB Output is correct
32 Correct 269 ms 603588 KB Output is correct
33 Correct 255 ms 603476 KB Output is correct
34 Correct 242 ms 603584 KB Output is correct
35 Correct 185 ms 602600 KB Output is correct
36 Correct 247 ms 603584 KB Output is correct
37 Correct 283 ms 603732 KB Output is correct
38 Correct 215 ms 602828 KB Output is correct
39 Correct 1109 ms 739932 KB Output is correct
40 Correct 276 ms 605440 KB Output is correct
41 Correct 250 ms 606652 KB Output is correct
42 Correct 258 ms 609364 KB Output is correct
43 Correct 239 ms 612280 KB Output is correct
44 Correct 602 ms 662908 KB Output is correct
45 Correct 576 ms 668980 KB Output is correct
46 Correct 1048 ms 740568 KB Output is correct
47 Correct 1067 ms 740176 KB Output is correct
48 Correct 1202 ms 740292 KB Output is correct
49 Correct 761 ms 740048 KB Output is correct
50 Correct 766 ms 739984 KB Output is correct
51 Correct 1221 ms 739988 KB Output is correct
52 Correct 1338 ms 740216 KB Output is correct
53 Correct 1349 ms 740144 KB Output is correct
54 Correct 136 ms 589464 KB Output is correct
55 Correct 158 ms 589424 KB Output is correct
56 Correct 199 ms 589504 KB Output is correct
57 Correct 199 ms 589276 KB Output is correct
58 Correct 200 ms 589536 KB Output is correct
59 Correct 198 ms 589496 KB Output is correct
60 Correct 196 ms 589396 KB Output is correct
61 Correct 195 ms 589376 KB Output is correct
62 Correct 203 ms 589396 KB Output is correct
63 Correct 192 ms 589396 KB Output is correct
64 Correct 200 ms 589396 KB Output is correct
65 Correct 215 ms 589492 KB Output is correct
66 Correct 198 ms 589396 KB Output is correct
67 Correct 213 ms 589360 KB Output is correct
68 Correct 190 ms 589556 KB Output is correct
69 Correct 192 ms 589384 KB Output is correct
70 Correct 214 ms 589516 KB Output is correct
71 Correct 140 ms 589400 KB Output is correct
72 Correct 179 ms 587604 KB Output is correct
73 Correct 176 ms 587344 KB Output is correct
74 Correct 139 ms 587344 KB Output is correct
75 Correct 242 ms 589616 KB Output is correct
76 Correct 193 ms 589336 KB Output is correct
77 Correct 188 ms 589396 KB Output is correct
78 Correct 188 ms 589392 KB Output is correct
79 Correct 192 ms 589428 KB Output is correct
80 Correct 193 ms 589356 KB Output is correct
81 Correct 190 ms 589392 KB Output is correct
82 Correct 184 ms 589500 KB Output is correct
83 Correct 135 ms 589392 KB Output is correct
84 Correct 241 ms 588936 KB Output is correct
85 Correct 248 ms 588628 KB Output is correct
86 Correct 182 ms 588628 KB Output is correct
87 Correct 195 ms 589376 KB Output is correct
88 Correct 191 ms 589500 KB Output is correct
89 Correct 174 ms 589396 KB Output is correct
90 Correct 197 ms 589360 KB Output is correct
91 Correct 188 ms 589288 KB Output is correct
92 Correct 182 ms 589508 KB Output is correct
93 Correct 189 ms 589392 KB Output is correct
94 Correct 182 ms 589392 KB Output is correct
95 Correct 186 ms 589588 KB Output is correct
96 Correct 185 ms 589344 KB Output is correct
97 Correct 182 ms 589396 KB Output is correct
98 Correct 177 ms 589384 KB Output is correct
99 Correct 175 ms 589396 KB Output is correct
100 Correct 179 ms 589500 KB Output is correct
101 Correct 198 ms 589800 KB Output is correct
102 Correct 137 ms 587344 KB Output is correct
103 Correct 151 ms 587508 KB Output is correct
104 Correct 141 ms 587408 KB Output is correct
105 Correct 168 ms 587348 KB Output is correct
106 Correct 211 ms 589608 KB Output is correct
107 Correct 194 ms 589436 KB Output is correct
108 Correct 206 ms 589636 KB Output is correct
109 Correct 203 ms 589652 KB Output is correct
110 Correct 207 ms 592980 KB Output is correct
111 Correct 249 ms 594596 KB Output is correct
112 Correct 225 ms 595084 KB Output is correct
113 Correct 213 ms 595024 KB Output is correct
114 Correct 224 ms 595116 KB Output is correct
115 Correct 239 ms 595116 KB Output is correct
116 Correct 262 ms 594944 KB Output is correct
117 Correct 264 ms 595068 KB Output is correct
118 Correct 165 ms 593596 KB Output is correct
119 Correct 192 ms 600820 KB Output is correct
120 Correct 201 ms 603472 KB Output is correct
121 Correct 223 ms 603404 KB Output is correct
122 Correct 223 ms 603608 KB Output is correct
123 Correct 229 ms 602140 KB Output is correct
124 Correct 495 ms 632112 KB Output is correct
125 Correct 1125 ms 717928 KB Output is correct
126 Correct 1258 ms 742000 KB Output is correct
127 Correct 1104 ms 742252 KB Output is correct
128 Correct 821 ms 738128 KB Output is correct
129 Correct 757 ms 736456 KB Output is correct
130 Correct 1312 ms 742052 KB Output is correct
131 Correct 1377 ms 743340 KB Output is correct
132 Correct 283 ms 593492 KB Output is correct
133 Correct 135 ms 589648 KB Output is correct
134 Correct 227 ms 587860 KB Output is correct
135 Correct 262 ms 591444 KB Output is correct
136 Correct 233 ms 593744 KB Output is correct
137 Correct 247 ms 594620 KB Output is correct
138 Correct 206 ms 595020 KB Output is correct
139 Correct 181 ms 593556 KB Output is correct
140 Correct 238 ms 593680 KB Output is correct
141 Correct 265 ms 593492 KB Output is correct
142 Correct 287 ms 594992 KB Output is correct
143 Correct 254 ms 595364 KB Output is correct
144 Correct 220 ms 594424 KB Output is correct
145 Correct 307 ms 593708 KB Output is correct
146 Correct 246 ms 595196 KB Output is correct
147 Correct 254 ms 595196 KB Output is correct
148 Correct 270 ms 595212 KB Output is correct
149 Correct 238 ms 595020 KB Output is correct
150 Correct 249 ms 595204 KB Output is correct
151 Correct 246 ms 595028 KB Output is correct
152 Correct 281 ms 593480 KB Output is correct
153 Correct 291 ms 593748 KB Output is correct
154 Correct 304 ms 603524 KB Output is correct
155 Correct 271 ms 593692 KB Output is correct
156 Correct 221 ms 599888 KB Output is correct
157 Correct 373 ms 601584 KB Output is correct
158 Correct 382 ms 602964 KB Output is correct
159 Correct 283 ms 603740 KB Output is correct
160 Correct 278 ms 603688 KB Output is correct
161 Correct 302 ms 603756 KB Output is correct
162 Correct 274 ms 603544 KB Output is correct
163 Correct 307 ms 603484 KB Output is correct
164 Correct 297 ms 603732 KB Output is correct
165 Correct 260 ms 603744 KB Output is correct
166 Correct 293 ms 603736 KB Output is correct
167 Correct 194 ms 603760 KB Output is correct
168 Correct 318 ms 603764 KB Output is correct
169 Correct 277 ms 603728 KB Output is correct
170 Correct 339 ms 602960 KB Output is correct
171 Correct 379 ms 602840 KB Output is correct
172 Correct 337 ms 602964 KB Output is correct
173 Correct 394 ms 603088 KB Output is correct
174 Correct 373 ms 607572 KB Output is correct
175 Correct 415 ms 623640 KB Output is correct
176 Correct 624 ms 665700 KB Output is correct
177 Correct 747 ms 690472 KB Output is correct
178 Correct 1057 ms 721912 KB Output is correct
179 Correct 943 ms 741588 KB Output is correct
180 Correct 995 ms 741676 KB Output is correct
181 Correct 1202 ms 741520 KB Output is correct
182 Correct 1275 ms 741752 KB Output is correct
183 Correct 1120 ms 743228 KB Output is correct

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 589348 KB Output is correct
2 Correct 193 ms 589396 KB Output is correct
3 Correct 194 ms 589572 KB Output is correct
4 Correct 192 ms 589368 KB Output is correct
5 Correct 135 ms 589356 KB Output is correct
6 Correct 249 ms 588624 KB Output is correct
7 Correct 237 ms 587636 KB Output is correct
8 Correct 147 ms 588484 KB Output is correct
9 Correct 243 ms 587344 KB Output is correct
10 Correct 233 ms 587536 KB Output is correct
11 Correct 194 ms 587528 KB Output is correct
12 Correct 239 ms 587344 KB Output is correct
13 Correct 245 ms 587348 KB Output is correct
14 Correct 245 ms 587504 KB Output is correct
15 Correct 193 ms 589396 KB Output is correct
16 Correct 182 ms 589592 KB Output is correct
17 Correct 142 ms 589392 KB Output is correct
18 Correct 190 ms 589420 KB Output is correct
19 Correct 251 ms 595024 KB Output is correct
20 Correct 179 ms 594108 KB Output is correct
21 Correct 207 ms 595032 KB Output is correct
22 Correct 209 ms 595136 KB Output is correct
23 Correct 217 ms 595120 KB Output is correct
24 Correct 197 ms 595068 KB Output is correct
25 Correct 173 ms 595044 KB Output is correct
26 Correct 205 ms 595024 KB Output is correct
27 Correct 205 ms 595072 KB Output is correct
28 Correct 202 ms 595128 KB Output is correct
29 Correct 245 ms 603544 KB Output is correct
30 Correct 222 ms 595084 KB Output is correct
31 Correct 246 ms 603628 KB Output is correct
32 Correct 269 ms 603588 KB Output is correct
33 Correct 255 ms 603476 KB Output is correct
34 Correct 242 ms 603584 KB Output is correct
35 Correct 185 ms 602600 KB Output is correct
36 Correct 247 ms 603584 KB Output is correct
37 Correct 283 ms 603732 KB Output is correct
38 Correct 215 ms 602828 KB Output is correct
39 Correct 1109 ms 739932 KB Output is correct
40 Correct 276 ms 605440 KB Output is correct
41 Correct 250 ms 606652 KB Output is correct
42 Correct 258 ms 609364 KB Output is correct
43 Correct 239 ms 612280 KB Output is correct
44 Correct 602 ms 662908 KB Output is correct
45 Correct 576 ms 668980 KB Output is correct
46 Correct 1048 ms 740568 KB Output is correct
47 Correct 1067 ms 740176 KB Output is correct
48 Correct 1202 ms 740292 KB Output is correct
49 Correct 761 ms 740048 KB Output is correct
50 Correct 766 ms 739984 KB Output is correct
51 Correct 1221 ms 739988 KB Output is correct
52 Correct 1338 ms 740216 KB Output is correct
53 Correct 1349 ms 740144 KB Output is correct
54 Correct 136 ms 589464 KB Output is correct
55 Correct 158 ms 589424 KB Output is correct
56 Correct 199 ms 589504 KB Output is correct
57 Correct 199 ms 589276 KB Output is correct
58 Correct 200 ms 589536 KB Output is correct
59 Correct 198 ms 589496 KB Output is correct
60 Correct 196 ms 589396 KB Output is correct
61 Correct 195 ms 589376 KB Output is correct
62 Correct 203 ms 589396 KB Output is correct
63 Correct 192 ms 589396 KB Output is correct
64 Correct 200 ms 589396 KB Output is correct
65 Correct 215 ms 589492 KB Output is correct
66 Correct 198 ms 589396 KB Output is correct
67 Correct 213 ms 589360 KB Output is correct
68 Correct 190 ms 589556 KB Output is correct
69 Correct 192 ms 589384 KB Output is correct
70 Correct 214 ms 589516 KB Output is correct
71 Correct 140 ms 589400 KB Output is correct
72 Correct 179 ms 587604 KB Output is correct
73 Correct 176 ms 587344 KB Output is correct
74 Correct 139 ms 587344 KB Output is correct
75 Correct 242 ms 589616 KB Output is correct
76 Correct 193 ms 589336 KB Output is correct
77 Correct 188 ms 589396 KB Output is correct
78 Correct 188 ms 589392 KB Output is correct
79 Correct 192 ms 589428 KB Output is correct
80 Correct 193 ms 589356 KB Output is correct
81 Correct 190 ms 589392 KB Output is correct
82 Correct 184 ms 589500 KB Output is correct
83 Correct 135 ms 589392 KB Output is correct
84 Correct 241 ms 588936 KB Output is correct
85 Correct 248 ms 588628 KB Output is correct
86 Correct 182 ms 588628 KB Output is correct
87 Correct 195 ms 589376 KB Output is correct
88 Correct 191 ms 589500 KB Output is correct
89 Correct 174 ms 589396 KB Output is correct
90 Correct 197 ms 589360 KB Output is correct
91 Correct 188 ms 589288 KB Output is correct
92 Correct 182 ms 589508 KB Output is correct
93 Correct 189 ms 589392 KB Output is correct
94 Correct 182 ms 589392 KB Output is correct
95 Correct 186 ms 589588 KB Output is correct
96 Correct 185 ms 589344 KB Output is correct
97 Correct 182 ms 589396 KB Output is correct
98 Correct 177 ms 589384 KB Output is correct
99 Correct 175 ms 589396 KB Output is correct
100 Correct 179 ms 589500 KB Output is correct
101 Correct 198 ms 589800 KB Output is correct
102 Correct 137 ms 587344 KB Output is correct
103 Correct 151 ms 587508 KB Output is correct
104 Correct 141 ms 587408 KB Output is correct
105 Correct 168 ms 587348 KB Output is correct
106 Correct 211 ms 589608 KB Output is correct
107 Correct 194 ms 589436 KB Output is correct
108 Correct 206 ms 589636 KB Output is correct
109 Correct 203 ms 589652 KB Output is correct
110 Correct 207 ms 592980 KB Output is correct
111 Correct 249 ms 594596 KB Output is correct
112 Correct 225 ms 595084 KB Output is correct
113 Correct 213 ms 595024 KB Output is correct
114 Correct 224 ms 595116 KB Output is correct
115 Correct 239 ms 595116 KB Output is correct
116 Correct 262 ms 594944 KB Output is correct
117 Correct 264 ms 595068 KB Output is correct
118 Correct 165 ms 593596 KB Output is correct
119 Correct 192 ms 600820 KB Output is correct
120 Correct 201 ms 603472 KB Output is correct
121 Correct 223 ms 603404 KB Output is correct
122 Correct 223 ms 603608 KB Output is correct
123 Correct 229 ms 602140 KB Output is correct
124 Correct 495 ms 632112 KB Output is correct
125 Correct 1125 ms 717928 KB Output is correct
126 Correct 1258 ms 742000 KB Output is correct
127 Correct 1104 ms 742252 KB Output is correct
128 Correct 821 ms 738128 KB Output is correct
129 Correct 757 ms 736456 KB Output is correct
130 Correct 1312 ms 742052 KB Output is correct
131 Correct 1377 ms 743340 KB Output is correct
132 Correct 283 ms 593492 KB Output is correct
133 Correct 135 ms 589648 KB Output is correct
134 Correct 227 ms 587860 KB Output is correct
135 Correct 262 ms 591444 KB Output is correct
136 Correct 233 ms 593744 KB Output is correct
137 Correct 247 ms 594620 KB Output is correct
138 Correct 206 ms 595020 KB Output is correct
139 Correct 181 ms 593556 KB Output is correct
140 Correct 238 ms 593680 KB Output is correct
141 Correct 265 ms 593492 KB Output is correct
142 Correct 287 ms 594992 KB Output is correct
143 Correct 254 ms 595364 KB Output is correct
144 Correct 220 ms 594424 KB Output is correct
145 Correct 307 ms 593708 KB Output is correct
146 Correct 246 ms 595196 KB Output is correct
147 Correct 254 ms 595196 KB Output is correct
148 Correct 270 ms 595212 KB Output is correct
149 Correct 238 ms 595020 KB Output is correct
150 Correct 249 ms 595204 KB Output is correct
151 Correct 246 ms 595028 KB Output is correct
152 Correct 281 ms 593480 KB Output is correct
153 Correct 291 ms 593748 KB Output is correct
154 Correct 304 ms 603524 KB Output is correct
155 Correct 271 ms 593692 KB Output is correct
156 Correct 221 ms 599888 KB Output is correct
157 Correct 373 ms 601584 KB Output is correct
158 Correct 382 ms 602964 KB Output is correct
159 Correct 283 ms 603740 KB Output is correct
160 Correct 278 ms 603688 KB Output is correct
161 Correct 302 ms 603756 KB Output is correct
162 Correct 274 ms 603544 KB Output is correct
163 Correct 307 ms 603484 KB Output is correct
164 Correct 297 ms 603732 KB Output is correct
165 Correct 260 ms 603744 KB Output is correct
166 Correct 293 ms 603736 KB Output is correct
167 Correct 194 ms 603760 KB Output is correct
168 Correct 318 ms 603764 KB Output is correct
169 Correct 277 ms 603728 KB Output is correct
170 Correct 339 ms 602960 KB Output is correct
171 Correct 379 ms 602840 KB Output is correct
172 Correct 337 ms 602964 KB Output is correct
173 Correct 394 ms 603088 KB Output is correct
174 Correct 373 ms 607572 KB Output is correct
175 Correct 415 ms 623640 KB Output is correct
176 Correct 624 ms 665700 KB Output is correct
177 Correct 747 ms 690472 KB Output is correct
178 Correct 1057 ms 721912 KB Output is correct
179 Correct 943 ms 741588 KB Output is correct
180 Correct 995 ms 741676 KB Output is correct
181 Correct 1202 ms 741520 KB Output is correct
182 Correct 1275 ms 741752 KB Output is correct
183 Correct 1120 ms 743228 KB Output is correct
184 Execution timed out 2094 ms 892780 KB Time limit exceeded
185 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 589348 KB Output is correct
2 Correct 193 ms 589396 KB Output is correct
3 Correct 194 ms 589572 KB Output is correct
4 Correct 192 ms 589368 KB Output is correct
5 Correct 135 ms 589356 KB Output is correct
6 Correct 249 ms 588624 KB Output is correct
7 Correct 237 ms 587636 KB Output is correct
8 Correct 147 ms 588484 KB Output is correct
9 Correct 243 ms 587344 KB Output is correct
10 Correct 233 ms 587536 KB Output is correct
11 Correct 194 ms 587528 KB Output is correct
12 Correct 239 ms 587344 KB Output is correct
13 Correct 245 ms 587348 KB Output is correct
14 Correct 245 ms 587504 KB Output is correct
15 Correct 193 ms 589396 KB Output is correct
16 Correct 182 ms 589592 KB Output is correct
17 Correct 142 ms 589392 KB Output is correct
18 Correct 190 ms 589420 KB Output is correct
19 Correct 251 ms 595024 KB Output is correct
20 Correct 179 ms 594108 KB Output is correct
21 Correct 207 ms 595032 KB Output is correct
22 Correct 209 ms 595136 KB Output is correct
23 Correct 217 ms 595120 KB Output is correct
24 Correct 197 ms 595068 KB Output is correct
25 Correct 173 ms 595044 KB Output is correct
26 Correct 205 ms 595024 KB Output is correct
27 Correct 205 ms 595072 KB Output is correct
28 Correct 202 ms 595128 KB Output is correct
29 Correct 245 ms 603544 KB Output is correct
30 Correct 222 ms 595084 KB Output is correct
31 Correct 246 ms 603628 KB Output is correct
32 Correct 269 ms 603588 KB Output is correct
33 Correct 255 ms 603476 KB Output is correct
34 Correct 242 ms 603584 KB Output is correct
35 Correct 185 ms 602600 KB Output is correct
36 Correct 247 ms 603584 KB Output is correct
37 Correct 283 ms 603732 KB Output is correct
38 Correct 215 ms 602828 KB Output is correct
39 Correct 1109 ms 739932 KB Output is correct
40 Correct 276 ms 605440 KB Output is correct
41 Correct 250 ms 606652 KB Output is correct
42 Correct 258 ms 609364 KB Output is correct
43 Correct 239 ms 612280 KB Output is correct
44 Correct 602 ms 662908 KB Output is correct
45 Correct 576 ms 668980 KB Output is correct
46 Correct 1048 ms 740568 KB Output is correct
47 Correct 1067 ms 740176 KB Output is correct
48 Correct 1202 ms 740292 KB Output is correct
49 Correct 761 ms 740048 KB Output is correct
50 Correct 766 ms 739984 KB Output is correct
51 Correct 1221 ms 739988 KB Output is correct
52 Correct 1338 ms 740216 KB Output is correct
53 Correct 1349 ms 740144 KB Output is correct
54 Correct 136 ms 589464 KB Output is correct
55 Correct 158 ms 589424 KB Output is correct
56 Correct 199 ms 589504 KB Output is correct
57 Correct 199 ms 589276 KB Output is correct
58 Correct 200 ms 589536 KB Output is correct
59 Correct 198 ms 589496 KB Output is correct
60 Correct 196 ms 589396 KB Output is correct
61 Correct 195 ms 589376 KB Output is correct
62 Correct 203 ms 589396 KB Output is correct
63 Correct 192 ms 589396 KB Output is correct
64 Correct 200 ms 589396 KB Output is correct
65 Correct 215 ms 589492 KB Output is correct
66 Correct 198 ms 589396 KB Output is correct
67 Correct 213 ms 589360 KB Output is correct
68 Correct 190 ms 589556 KB Output is correct
69 Correct 192 ms 589384 KB Output is correct
70 Correct 214 ms 589516 KB Output is correct
71 Correct 140 ms 589400 KB Output is correct
72 Correct 179 ms 587604 KB Output is correct
73 Correct 176 ms 587344 KB Output is correct
74 Correct 139 ms 587344 KB Output is correct
75 Correct 242 ms 589616 KB Output is correct
76 Correct 193 ms 589336 KB Output is correct
77 Correct 188 ms 589396 KB Output is correct
78 Correct 188 ms 589392 KB Output is correct
79 Correct 192 ms 589428 KB Output is correct
80 Correct 193 ms 589356 KB Output is correct
81 Correct 190 ms 589392 KB Output is correct
82 Correct 184 ms 589500 KB Output is correct
83 Correct 135 ms 589392 KB Output is correct
84 Correct 241 ms 588936 KB Output is correct
85 Correct 248 ms 588628 KB Output is correct
86 Correct 182 ms 588628 KB Output is correct
87 Correct 195 ms 589376 KB Output is correct
88 Correct 191 ms 589500 KB Output is correct
89 Correct 174 ms 589396 KB Output is correct
90 Correct 197 ms 589360 KB Output is correct
91 Correct 188 ms 589288 KB Output is correct
92 Correct 182 ms 589508 KB Output is correct
93 Correct 189 ms 589392 KB Output is correct
94 Correct 182 ms 589392 KB Output is correct
95 Correct 186 ms 589588 KB Output is correct
96 Correct 185 ms 589344 KB Output is correct
97 Correct 182 ms 589396 KB Output is correct
98 Correct 177 ms 589384 KB Output is correct
99 Correct 175 ms 589396 KB Output is correct
100 Correct 179 ms 589500 KB Output is correct
101 Correct 198 ms 589800 KB Output is correct
102 Correct 137 ms 587344 KB Output is correct
103 Correct 151 ms 587508 KB Output is correct
104 Correct 141 ms 587408 KB Output is correct
105 Correct 168 ms 587348 KB Output is correct
106 Correct 211 ms 589608 KB Output is correct
107 Correct 194 ms 589436 KB Output is correct
108 Correct 206 ms 589636 KB Output is correct
109 Correct 203 ms 589652 KB Output is correct
110 Correct 207 ms 592980 KB Output is correct
111 Correct 249 ms 594596 KB Output is correct
112 Correct 225 ms 595084 KB Output is correct
113 Correct 213 ms 595024 KB Output is correct
114 Correct 224 ms 595116 KB Output is correct
115 Correct 239 ms 595116 KB Output is correct
116 Correct 262 ms 594944 KB Output is correct
117 Correct 264 ms 595068 KB Output is correct
118 Correct 165 ms 593596 KB Output is correct
119 Correct 192 ms 600820 KB Output is correct
120 Correct 201 ms 603472 KB Output is correct
121 Correct 223 ms 603404 KB Output is correct
122 Correct 223 ms 603608 KB Output is correct
123 Correct 229 ms 602140 KB Output is correct
124 Correct 495 ms 632112 KB Output is correct
125 Correct 1125 ms 717928 KB Output is correct
126 Correct 1258 ms 742000 KB Output is correct
127 Correct 1104 ms 742252 KB Output is correct
128 Correct 821 ms 738128 KB Output is correct
129 Correct 757 ms 736456 KB Output is correct
130 Correct 1312 ms 742052 KB Output is correct
131 Correct 1377 ms 743340 KB Output is correct
132 Correct 283 ms 593492 KB Output is correct
133 Correct 135 ms 589648 KB Output is correct
134 Correct 227 ms 587860 KB Output is correct
135 Correct 262 ms 591444 KB Output is correct
136 Correct 233 ms 593744 KB Output is correct
137 Correct 247 ms 594620 KB Output is correct
138 Correct 206 ms 595020 KB Output is correct
139 Correct 181 ms 593556 KB Output is correct
140 Correct 238 ms 593680 KB Output is correct
141 Correct 265 ms 593492 KB Output is correct
142 Correct 287 ms 594992 KB Output is correct
143 Correct 254 ms 595364 KB Output is correct
144 Correct 220 ms 594424 KB Output is correct
145 Correct 307 ms 593708 KB Output is correct
146 Correct 246 ms 595196 KB Output is correct
147 Correct 254 ms 595196 KB Output is correct
148 Correct 270 ms 595212 KB Output is correct
149 Correct 238 ms 595020 KB Output is correct
150 Correct 249 ms 595204 KB Output is correct
151 Correct 246 ms 595028 KB Output is correct
152 Correct 281 ms 593480 KB Output is correct
153 Correct 291 ms 593748 KB Output is correct
154 Correct 304 ms 603524 KB Output is correct
155 Correct 271 ms 593692 KB Output is correct
156 Correct 221 ms 599888 KB Output is correct
157 Correct 373 ms 601584 KB Output is correct
158 Correct 382 ms 602964 KB Output is correct
159 Correct 283 ms 603740 KB Output is correct
160 Correct 278 ms 603688 KB Output is correct
161 Correct 302 ms 603756 KB Output is correct
162 Correct 274 ms 603544 KB Output is correct
163 Correct 307 ms 603484 KB Output is correct
164 Correct 297 ms 603732 KB Output is correct
165 Correct 260 ms 603744 KB Output is correct
166 Correct 293 ms 603736 KB Output is correct
167 Correct 194 ms 603760 KB Output is correct
168 Correct 318 ms 603764 KB Output is correct
169 Correct 277 ms 603728 KB Output is correct
170 Correct 339 ms 602960 KB Output is correct
171 Correct 379 ms 602840 KB Output is correct
172 Correct 337 ms 602964 KB Output is correct
173 Correct 394 ms 603088 KB Output is correct
174 Correct 373 ms 607572 KB Output is correct
175 Correct 415 ms 623640 KB Output is correct
176 Correct 624 ms 665700 KB Output is correct
177 Correct 747 ms 690472 KB Output is correct
178 Correct 1057 ms 721912 KB Output is correct
179 Correct 943 ms 741588 KB Output is correct
180 Correct 995 ms 741676 KB Output is correct
181 Correct 1202 ms 741520 KB Output is correct
182 Correct 1275 ms 741752 KB Output is correct
183 Correct 1120 ms 743228 KB Output is correct
184 Execution timed out 2094 ms 892780 KB Time limit exceeded
185 Halted 0 ms 0 KB -