oj.uz

Submission #1084518

# Submission time Handle Problem Language Result Execution time Memory
1084518 2024-09-06T10:57:15 Z peacebringer1667 Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 131 ms 234420 KB 
#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 3e4 + 5;

int B[maxn],P[maxn];
void input(int n){
    for (int i = 0 ; i < n ; i++)
      cin >> B[i] >> P[i];
}

namespace sub1{
	const int K = 2e3 + 5;
	bool check(int n){
		return (n <= K);
	}
	
	bool mark[K][K],vis[K];
	int dp[K];
	
	vector <vector<pir>> vec(100*K);
	vector <vector<int>> doge(K);

	void bfs(int n,int N){
		vec[0].push_back({B[0],P[0]});
	    
	    for (int len = 0 ; len < 100*N ; len++)
	      for (pir t : vec[len]){
	      	int Bi = t.fi,Pi = t.se;
			if (mark[Bi][Pi]) continue;
			
	      	mark[Bi][Pi] = 1;
	      	if (!vis[Bi])
			   dp[Bi] = len;
	      	
	      	if (Bi + Pi < N)
	      		vec[len + 1].push_back({Bi + Pi,Pi});
	      	if (Bi - Pi >= 0)
	      	    vec[len + 1].push_back({Bi - Pi,Pi});
	      	
	      	if (!vis[Bi])
	      	  for (int p : doge[Bi]){
	      	  	  if (Bi + p < N)
	      	  	    vec[len + 1].push_back({Bi + p,p});
	      	  	  if (Bi - p >= 0)
	      	  	    vec[len + 1].push_back({Bi - p,p});
				}
			
			vis[Bi] = 1;
		  }
	}
	
	int solve(int n,int N){
		//dp[i][k] : position i, jump k
		for (int i = 0 ; i < n ; i++)
		  doge[B[i]].push_back(P[i]);
		
		bfs(n,N);
		
		if (!vis[B[1]]) return -1;
		return dp[B[1]];
	}
}

namespace sub2{
	const int block = 150;
	
	bool vis[maxn];
	bool mark[maxn][block];
	int dp[maxn];
	
	vector <vector<pir>> vec(maxn*block);
	vector <vector<int>> doge(maxn);
	
	void bfs(int n,int N){
		vec[0].push_back({B[0],P[0]});
		
		for (int len = 0 ; len < N * block ; len++)
		  for (pir t : vec[len]){
		  	int Bi = t.fi,Pi = t.se;
		  	
		  	if (Pi <= block && mark[Bi][Pi]) continue;
		  	if (Pi <= block) mark[Bi][Pi] = 1;
		  	
			if (!vis[Bi]) dp[Bi] = len;
		  	
		  	if (!vis[Bi])
		  	for (int p : doge[Bi])
		  	  if (p > block){
		  	     for (int x = Bi + p ; x < N ; x += p)
		  	       if (x < N && !vis[x])
		  	       	vec[len + (x - Bi)/p].push_back({x,p});
			     
			     for (int x = Bi - p ; x >= 0 ; x -= p)
			       if (x >= 0 && !vis[x])
			         vec[len + (Bi - x)/p].push_back({x,p});
			  }
			if (!vis[Bi])
	      	  for (int p : doge[Bi]) 
				 if (p <= block){
	      	  	  if (Bi + p < N)
	      	  	    vec[len + 1].push_back({Bi + p,p});
	      	  	  if (Bi - p >= 0)
	      	  	    vec[len + 1].push_back({Bi - p,p});
				}
		    
		    if (Pi <= block && Bi + Pi < N)
		      vec[len + 1].push_back({Bi + Pi,Pi});
		    
		    if (Pi <= block && Bi - Pi >= 0)
		      vec[len + 1].push_back({Bi - Pi,Pi});
			
			vis[Bi] = 1;
		  }
	}
	
	int solve(int n,int N){
		for (int i = 0 ; i < n ; i++)
		  doge[B[i]].push_back(P[i]);
		
		bfs(n,N);
		
		if (!vis[B[1]]) return -1;
		return dp[B[1]];
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int N,n;
	cin >> N >> n;
	input(n);
	
	if (sub1::check(n))
	  cout << sub1::solve(n,N);else
	
	cout << sub2::solve(n,N);
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 111444 KB Output is correct
2 Correct 50 ms 111616 KB Output is correct
3 Correct 49 ms 111444 KB Output is correct
4 Correct 47 ms 111452 KB Output is correct
5 Correct 50 ms 111444 KB Output is correct
6 Correct 49 ms 111420 KB Output is correct
7 Correct 45 ms 111440 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 111440 KB Output is correct
2 Correct 46 ms 111440 KB Output is correct
3 Correct 46 ms 111444 KB Output is correct
4 Correct 46 ms 111444 KB Output is correct
5 Correct 46 ms 111444 KB Output is correct
6 Correct 49 ms 111444 KB Output is correct
7 Correct 45 ms 111444 KB Output is correct
8 Correct 44 ms 111444 KB Output is correct
9 Correct 46 ms 111696 KB Output is correct
10 Correct 44 ms 111700 KB Output is correct
11 Correct 52 ms 111952 KB Output is correct
12 Correct 50 ms 111696 KB Output is correct
13 Correct 46 ms 111700 KB Output is correct
14 Correct 44 ms 111956 KB Output is correct
15 Correct 47 ms 111956 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 111444 KB Output is correct
2 Correct 52 ms 111444 KB Output is correct
3 Correct 48 ms 111616 KB Output is correct
4 Correct 48 ms 111440 KB Output is correct
5 Correct 50 ms 111452 KB Output is correct
6 Correct 47 ms 111540 KB Output is correct
7 Correct 46 ms 111452 KB Output is correct
8 Correct 45 ms 111444 KB Output is correct
9 Correct 46 ms 111696 KB Output is correct
10 Correct 48 ms 111700 KB Output is correct
11 Correct 48 ms 111696 KB Output is correct
12 Correct 48 ms 111696 KB Output is correct
13 Correct 47 ms 111728 KB Output is correct
14 Correct 47 ms 111952 KB Output is correct
15 Correct 45 ms 111956 KB Output is correct
16 Correct 51 ms 111444 KB Output is correct
17 Correct 52 ms 113236 KB Output is correct
18 Correct 50 ms 111444 KB Output is correct
19 Correct 45 ms 111700 KB Output is correct
20 Correct 56 ms 115540 KB Output is correct
21 Correct 50 ms 111528 KB Output is correct
22 Correct 45 ms 111452 KB Output is correct
23 Correct 51 ms 114780 KB Output is correct
24 Correct 49 ms 115648 KB Output is correct
25 Correct 51 ms 115568 KB Output is correct
26 Correct 53 ms 115796 KB Output is correct
27 Correct 51 ms 115800 KB Output is correct
28 Correct 48 ms 116048 KB Output is correct
29 Correct 52 ms 116564 KB Output is correct
30 Correct 46 ms 115880 KB Output is correct
31 Correct 54 ms 116048 KB Output is correct
32 Correct 46 ms 116048 KB Output is correct
33 Correct 53 ms 117708 KB Output is correct
34 Correct 48 ms 117584 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 111572 KB Output is correct
2 Correct 48 ms 111452 KB Output is correct
3 Correct 48 ms 111444 KB Output is correct
4 Correct 47 ms 111444 KB Output is correct
5 Correct 51 ms 111452 KB Output is correct
6 Correct 46 ms 111444 KB Output is correct
7 Correct 48 ms 111444 KB Output is correct
8 Correct 50 ms 111640 KB Output is correct
9 Correct 53 ms 111700 KB Output is correct
10 Correct 44 ms 111696 KB Output is correct
11 Correct 46 ms 111896 KB Output is correct
12 Correct 47 ms 111700 KB Output is correct
13 Correct 49 ms 111776 KB Output is correct
14 Correct 49 ms 111820 KB Output is correct
15 Correct 48 ms 111732 KB Output is correct
16 Correct 53 ms 111440 KB Output is correct
17 Correct 50 ms 113232 KB Output is correct
18 Correct 44 ms 111552 KB Output is correct
19 Correct 47 ms 111484 KB Output is correct
20 Correct 48 ms 115536 KB Output is correct
21 Correct 44 ms 111532 KB Output is correct
22 Correct 48 ms 111452 KB Output is correct
23 Correct 47 ms 114772 KB Output is correct
24 Correct 50 ms 115540 KB Output is correct
25 Correct 50 ms 115540 KB Output is correct
26 Correct 48 ms 115712 KB Output is correct
27 Correct 46 ms 115732 KB Output is correct
28 Correct 51 ms 116304 KB Output is correct
29 Correct 59 ms 116564 KB Output is correct
30 Correct 48 ms 115796 KB Output is correct
31 Correct 52 ms 116256 KB Output is correct
32 Correct 52 ms 116036 KB Output is correct
33 Correct 51 ms 117752 KB Output is correct
34 Correct 53 ms 117760 KB Output is correct
35 Correct 56 ms 113484 KB Output is correct
36 Correct 47 ms 111952 KB Output is correct
37 Correct 54 ms 114288 KB Output is correct
38 Correct 54 ms 114264 KB Output is correct
39 Correct 57 ms 114196 KB Output is correct
40 Correct 56 ms 114212 KB Output is correct
41 Correct 53 ms 114256 KB Output is correct
42 Correct 50 ms 113068 KB Output is correct
43 Correct 52 ms 113108 KB Output is correct
44 Correct 53 ms 113100 KB Output is correct
45 Correct 63 ms 118544 KB Output is correct
46 Correct 60 ms 118736 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 111444 KB Output is correct
2 Correct 43 ms 111440 KB Output is correct
3 Correct 47 ms 111440 KB Output is correct
4 Correct 47 ms 111512 KB Output is correct
5 Correct 52 ms 111700 KB Output is correct
6 Correct 43 ms 111440 KB Output is correct
7 Correct 46 ms 111440 KB Output is correct
8 Correct 50 ms 111700 KB Output is correct
9 Correct 45 ms 111676 KB Output is correct
10 Correct 46 ms 111696 KB Output is correct
11 Correct 53 ms 111884 KB Output is correct
12 Correct 48 ms 111700 KB Output is correct
13 Correct 44 ms 111700 KB Output is correct
14 Correct 49 ms 111964 KB Output is correct
15 Correct 50 ms 111952 KB Output is correct
16 Correct 52 ms 111444 KB Output is correct
17 Correct 54 ms 113356 KB Output is correct
18 Correct 46 ms 111696 KB Output is correct
19 Correct 47 ms 111700 KB Output is correct
20 Correct 50 ms 115684 KB Output is correct
21 Correct 45 ms 111440 KB Output is correct
22 Correct 50 ms 111464 KB Output is correct
23 Correct 47 ms 114768 KB Output is correct
24 Correct 51 ms 115536 KB Output is correct
25 Correct 52 ms 115540 KB Output is correct
26 Correct 47 ms 115792 KB Output is correct
27 Correct 50 ms 115588 KB Output is correct
28 Correct 51 ms 116232 KB Output is correct
29 Correct 50 ms 116560 KB Output is correct
30 Correct 53 ms 115716 KB Output is correct
31 Correct 50 ms 116052 KB Output is correct
32 Correct 52 ms 116040 KB Output is correct
33 Correct 55 ms 117764 KB Output is correct
34 Correct 56 ms 117588 KB Output is correct
35 Correct 54 ms 113488 KB Output is correct
36 Correct 53 ms 111952 KB Output is correct
37 Correct 55 ms 114284 KB Output is correct
38 Correct 55 ms 114268 KB Output is correct
39 Correct 55 ms 114448 KB Output is correct
40 Correct 56 ms 114212 KB Output is correct
41 Correct 55 ms 114256 KB Output is correct
42 Correct 52 ms 113148 KB Output is correct
43 Correct 57 ms 113104 KB Output is correct
44 Correct 52 ms 113156 KB Output is correct
45 Correct 62 ms 118516 KB Output is correct
46 Correct 61 ms 118496 KB Output is correct
47 Correct 70 ms 123212 KB Output is correct
48 Correct 59 ms 112468 KB Output is correct
49 Correct 58 ms 112464 KB Output is correct
50 Correct 64 ms 112208 KB Output is correct
51 Correct 74 ms 121424 KB Output is correct
52 Correct 75 ms 121940 KB Output is correct
53 Correct 66 ms 118864 KB Output is correct
54 Runtime error 131 ms 234420 KB Execution killed with signal 11
55 Halted 0 ms 0 KB -