oj.uz

Submission #1110835

# Submission time Handle Problem Language Result Execution time Memory
1110835 2024-11-10T15:16:30 Z peacebringer1667 Jakarta Skyscrapers (APIO15_skyscraper) C++17
100 / 100
 264 ms 217304 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 + 10);
	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);

	cout << sub2::solve(n,N);
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 113488 KB Output is correct
2 Correct 21 ms 113488 KB Output is correct
3 Correct 22 ms 113488 KB Output is correct
4 Correct 22 ms 113488 KB Output is correct
5 Correct 23 ms 113488 KB Output is correct
6 Correct 22 ms 113488 KB Output is correct
7 Correct 23 ms 113656 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 113624 KB Output is correct
2 Correct 23 ms 113488 KB Output is correct
3 Correct 21 ms 113488 KB Output is correct
4 Correct 32 ms 113488 KB Output is correct
5 Correct 40 ms 113480 KB Output is correct
6 Correct 27 ms 113488 KB Output is correct
7 Correct 31 ms 113644 KB Output is correct
8 Correct 33 ms 113500 KB Output is correct
9 Correct 27 ms 113500 KB Output is correct
10 Correct 31 ms 113500 KB Output is correct
11 Correct 30 ms 113796 KB Output is correct
12 Correct 34 ms 113744 KB Output is correct
13 Correct 34 ms 113744 KB Output is correct
14 Correct 29 ms 113748 KB Output is correct
15 Correct 31 ms 113744 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 113484 KB Output is correct
2 Correct 35 ms 113488 KB Output is correct
3 Correct 40 ms 113480 KB Output is correct
4 Correct 33 ms 113488 KB Output is correct
5 Correct 33 ms 113440 KB Output is correct
6 Correct 31 ms 113488 KB Output is correct
7 Correct 44 ms 113472 KB Output is correct
8 Correct 27 ms 113488 KB Output is correct
9 Correct 29 ms 113828 KB Output is correct
10 Correct 31 ms 113592 KB Output is correct
11 Correct 28 ms 113736 KB Output is correct
12 Correct 27 ms 113744 KB Output is correct
13 Correct 23 ms 113744 KB Output is correct
14 Correct 28 ms 113744 KB Output is correct
15 Correct 30 ms 113744 KB Output is correct
16 Correct 29 ms 113488 KB Output is correct
17 Correct 32 ms 114012 KB Output is correct
18 Correct 32 ms 113500 KB Output is correct
19 Correct 29 ms 113480 KB Output is correct
20 Correct 33 ms 113992 KB Output is correct
21 Correct 29 ms 113488 KB Output is correct
22 Correct 30 ms 113528 KB Output is correct
23 Correct 34 ms 114000 KB Output is correct
24 Correct 35 ms 114008 KB Output is correct
25 Correct 38 ms 113992 KB Output is correct
26 Correct 36 ms 114248 KB Output is correct
27 Correct 36 ms 114016 KB Output is correct
28 Correct 44 ms 114504 KB Output is correct
29 Correct 40 ms 115024 KB Output is correct
30 Correct 35 ms 114248 KB Output is correct
31 Correct 37 ms 114504 KB Output is correct
32 Correct 48 ms 114504 KB Output is correct
33 Correct 41 ms 116048 KB Output is correct
34 Correct 38 ms 116048 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 113564 KB Output is correct
2 Correct 37 ms 113488 KB Output is correct
3 Correct 41 ms 113480 KB Output is correct
4 Correct 42 ms 113480 KB Output is correct
5 Correct 43 ms 113656 KB Output is correct
6 Correct 46 ms 113480 KB Output is correct
7 Correct 35 ms 113660 KB Output is correct
8 Correct 46 ms 113624 KB Output is correct
9 Correct 33 ms 113488 KB Output is correct
10 Correct 40 ms 113488 KB Output is correct
11 Correct 44 ms 113764 KB Output is correct
12 Correct 32 ms 113756 KB Output is correct
13 Correct 34 ms 113760 KB Output is correct
14 Correct 32 ms 113736 KB Output is correct
15 Correct 38 ms 113736 KB Output is correct
16 Correct 44 ms 113492 KB Output is correct
17 Correct 42 ms 114020 KB Output is correct
18 Correct 39 ms 113592 KB Output is correct
19 Correct 41 ms 113584 KB Output is correct
20 Correct 37 ms 114000 KB Output is correct
21 Correct 43 ms 113544 KB Output is correct
22 Correct 41 ms 113480 KB Output is correct
23 Correct 49 ms 113996 KB Output is correct
24 Correct 34 ms 114144 KB Output is correct
25 Correct 33 ms 114000 KB Output is correct
26 Correct 45 ms 114256 KB Output is correct
27 Correct 33 ms 114076 KB Output is correct
28 Correct 45 ms 114432 KB Output is correct
29 Correct 43 ms 115016 KB Output is correct
30 Correct 41 ms 114248 KB Output is correct
31 Correct 42 ms 114520 KB Output is correct
32 Correct 39 ms 114276 KB Output is correct
33 Correct 56 ms 116040 KB Output is correct
34 Correct 44 ms 116040 KB Output is correct
35 Correct 45 ms 115216 KB Output is correct
36 Correct 41 ms 113992 KB Output is correct
37 Correct 42 ms 116324 KB Output is correct
38 Correct 40 ms 116048 KB Output is correct
39 Correct 56 ms 115980 KB Output is correct
40 Correct 49 ms 116136 KB Output is correct
41 Correct 44 ms 116304 KB Output is correct
42 Correct 36 ms 115160 KB Output is correct
43 Correct 41 ms 115024 KB Output is correct
44 Correct 37 ms 115148 KB Output is correct
45 Correct 52 ms 120528 KB Output is correct
46 Correct 52 ms 120536 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 113488 KB Output is correct
2 Correct 40 ms 113488 KB Output is correct
3 Correct 32 ms 113480 KB Output is correct
4 Correct 37 ms 113488 KB Output is correct
5 Correct 33 ms 113480 KB Output is correct
6 Correct 33 ms 113500 KB Output is correct
7 Correct 38 ms 113496 KB Output is correct
8 Correct 41 ms 113488 KB Output is correct
9 Correct 36 ms 113480 KB Output is correct
10 Correct 37 ms 113500 KB Output is correct
11 Correct 37 ms 113780 KB Output is correct
12 Correct 39 ms 113744 KB Output is correct
13 Correct 36 ms 113644 KB Output is correct
14 Correct 45 ms 113724 KB Output is correct
15 Correct 36 ms 113756 KB Output is correct
16 Correct 32 ms 113480 KB Output is correct
17 Correct 31 ms 114000 KB Output is correct
18 Correct 33 ms 113608 KB Output is correct
19 Correct 31 ms 113660 KB Output is correct
20 Correct 32 ms 114000 KB Output is correct
21 Correct 39 ms 113636 KB Output is correct
22 Correct 44 ms 113504 KB Output is correct
23 Correct 36 ms 113992 KB Output is correct
24 Correct 43 ms 113992 KB Output is correct
25 Correct 42 ms 113992 KB Output is correct
26 Correct 41 ms 114128 KB Output is correct
27 Correct 41 ms 114000 KB Output is correct
28 Correct 37 ms 114504 KB Output is correct
29 Correct 39 ms 115024 KB Output is correct
30 Correct 46 ms 114248 KB Output is correct
31 Correct 41 ms 114512 KB Output is correct
32 Correct 46 ms 114380 KB Output is correct
33 Correct 43 ms 116112 KB Output is correct
34 Correct 43 ms 116040 KB Output is correct
35 Correct 52 ms 115144 KB Output is correct
36 Correct 51 ms 113980 KB Output is correct
37 Correct 54 ms 116260 KB Output is correct
38 Correct 56 ms 115984 KB Output is correct
39 Correct 85 ms 115992 KB Output is correct
40 Correct 70 ms 115988 KB Output is correct
41 Correct 77 ms 116040 KB Output is correct
42 Correct 94 ms 114888 KB Output is correct
43 Correct 93 ms 114884 KB Output is correct
44 Correct 89 ms 115100 KB Output is correct
45 Correct 91 ms 120464 KB Output is correct
46 Correct 108 ms 120556 KB Output is correct
47 Correct 100 ms 125232 KB Output is correct
48 Correct 83 ms 114240 KB Output is correct
49 Correct 32 ms 114256 KB Output is correct
50 Correct 36 ms 114000 KB Output is correct
51 Correct 48 ms 122952 KB Output is correct
52 Correct 51 ms 123728 KB Output is correct
53 Correct 46 ms 120136 KB Output is correct
54 Correct 46 ms 118352 KB Output is correct
55 Correct 41 ms 118608 KB Output is correct
56 Correct 52 ms 120372 KB Output is correct
57 Correct 59 ms 126728 KB Output is correct
58 Correct 40 ms 120520 KB Output is correct
59 Correct 49 ms 121660 KB Output is correct
60 Correct 54 ms 121792 KB Output is correct
61 Correct 47 ms 121040 KB Output is correct
62 Correct 72 ms 127952 KB Output is correct
63 Correct 73 ms 128744 KB Output is correct
64 Correct 85 ms 130156 KB Output is correct
65 Correct 123 ms 154580 KB Output is correct
66 Correct 264 ms 217268 KB Output is correct
67 Correct 222 ms 217304 KB Output is correct