답안 #1084515

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1084515	2024-09-06T10:55:14 Z	peacebringer1667	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1000 ms	262144 KB

skyscraper

#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 = sqrt(maxn);
	
	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

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	127824 KB	Output is correct
2	Correct	53 ms	127824 KB	Output is correct
3	Correct	51 ms	127828 KB	Output is correct
4	Correct	49 ms	127824 KB	Output is correct
5	Correct	56 ms	127824 KB	Output is correct
6	Correct	53 ms	127756 KB	Output is correct
7	Correct	53 ms	127836 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	127828 KB	Output is correct
2	Correct	49 ms	127824 KB	Output is correct
3	Correct	52 ms	127828 KB	Output is correct
4	Correct	52 ms	127824 KB	Output is correct
5	Correct	58 ms	127828 KB	Output is correct
6	Correct	52 ms	127828 KB	Output is correct
7	Correct	50 ms	127724 KB	Output is correct
8	Correct	54 ms	127828 KB	Output is correct
9	Correct	59 ms	127828 KB	Output is correct
10	Correct	53 ms	127828 KB	Output is correct
11	Correct	54 ms	127996 KB	Output is correct
12	Correct	52 ms	128080 KB	Output is correct
13	Correct	61 ms	128084 KB	Output is correct
14	Correct	53 ms	128080 KB	Output is correct
15	Correct	56 ms	127952 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	53 ms	128080 KB	Output is correct
2	Correct	53 ms	127616 KB	Output is correct
3	Correct	57 ms	127824 KB	Output is correct
4	Correct	56 ms	127828 KB	Output is correct
5	Correct	52 ms	127832 KB	Output is correct
6	Correct	54 ms	127828 KB	Output is correct
7	Correct	57 ms	127828 KB	Output is correct
8	Correct	64 ms	127684 KB	Output is correct
9	Correct	56 ms	127908 KB	Output is correct
10	Correct	53 ms	127824 KB	Output is correct
11	Correct	54 ms	128080 KB	Output is correct
12	Correct	55 ms	128080 KB	Output is correct
13	Correct	56 ms	128084 KB	Output is correct
14	Correct	56 ms	128080 KB	Output is correct
15	Correct	72 ms	128080 KB	Output is correct
16	Correct	56 ms	127632 KB	Output is correct
17	Correct	59 ms	129472 KB	Output is correct
18	Correct	54 ms	127824 KB	Output is correct
19	Correct	53 ms	127828 KB	Output is correct
20	Correct	56 ms	131928 KB	Output is correct
21	Correct	56 ms	127676 KB	Output is correct
22	Correct	55 ms	127824 KB	Output is correct
23	Correct	55 ms	131156 KB	Output is correct
24	Correct	60 ms	131668 KB	Output is correct
25	Correct	71 ms	131964 KB	Output is correct
26	Correct	61 ms	132020 KB	Output is correct
27	Correct	56 ms	131924 KB	Output is correct
28	Correct	68 ms	132432 KB	Output is correct
29	Correct	56 ms	132944 KB	Output is correct
30	Correct	59 ms	131924 KB	Output is correct
31	Correct	59 ms	132308 KB	Output is correct
32	Correct	64 ms	132176 KB	Output is correct
33	Correct	59 ms	133968 KB	Output is correct
34	Correct	58 ms	133968 KB	Output is correct

Subtask #4
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	64 ms	127604 KB	Output is correct
2	Correct	54 ms	127828 KB	Output is correct
3	Correct	56 ms	127824 KB	Output is correct
4	Correct	62 ms	127732 KB	Output is correct
5	Correct	53 ms	127824 KB	Output is correct
6	Correct	50 ms	127828 KB	Output is correct
7	Correct	55 ms	127828 KB	Output is correct
8	Correct	53 ms	127832 KB	Output is correct
9	Correct	55 ms	127780 KB	Output is correct
10	Correct	57 ms	127940 KB	Output is correct
11	Correct	51 ms	127924 KB	Output is correct
12	Correct	51 ms	128088 KB	Output is correct
13	Correct	52 ms	128084 KB	Output is correct
14	Correct	52 ms	128084 KB	Output is correct
15	Correct	52 ms	128080 KB	Output is correct
16	Correct	46 ms	127828 KB	Output is correct
17	Correct	53 ms	129620 KB	Output is correct
18	Correct	50 ms	127836 KB	Output is correct
19	Correct	53 ms	127756 KB	Output is correct
20	Correct	55 ms	131820 KB	Output is correct
21	Correct	69 ms	127620 KB	Output is correct
22	Correct	56 ms	127836 KB	Output is correct
23	Correct	61 ms	131020 KB	Output is correct
24	Correct	55 ms	131792 KB	Output is correct
25	Correct	60 ms	131812 KB	Output is correct
26	Correct	56 ms	131924 KB	Output is correct
27	Correct	55 ms	131920 KB	Output is correct
28	Correct	56 ms	132432 KB	Output is correct
29	Correct	61 ms	132956 KB	Output is correct
30	Correct	57 ms	131920 KB	Output is correct
31	Correct	72 ms	132524 KB	Output is correct
32	Correct	53 ms	132180 KB	Output is correct
33	Correct	76 ms	133968 KB	Output is correct
34	Correct	60 ms	133972 KB	Output is correct
35	Correct	59 ms	129824 KB	Output is correct
36	Correct	59 ms	128240 KB	Output is correct
37	Correct	60 ms	130576 KB	Output is correct
38	Correct	62 ms	130640 KB	Output is correct
39	Correct	60 ms	130644 KB	Output is correct
40	Correct	62 ms	130564 KB	Output is correct
41	Correct	62 ms	130564 KB	Output is correct
42	Correct	60 ms	129492 KB	Output is correct
43	Correct	56 ms	129488 KB	Output is correct
44	Correct	55 ms	129372 KB	Output is correct
45	Correct	69 ms	135192 KB	Output is correct
46	Correct	68 ms	135452 KB	Output is correct

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	52 ms	127744 KB	Output is correct
2	Correct	62 ms	127820 KB	Output is correct
3	Correct	62 ms	127828 KB	Output is correct
4	Correct	53 ms	127824 KB	Output is correct
5	Correct	59 ms	127848 KB	Output is correct
6	Correct	60 ms	127828 KB	Output is correct
7	Correct	55 ms	127828 KB	Output is correct
8	Correct	51 ms	127824 KB	Output is correct
9	Correct	55 ms	127820 KB	Output is correct
10	Correct	51 ms	127828 KB	Output is correct
11	Correct	55 ms	128084 KB	Output is correct
12	Correct	75 ms	128080 KB	Output is correct
13	Correct	57 ms	128080 KB	Output is correct
14	Correct	54 ms	128084 KB	Output is correct
15	Correct	56 ms	128080 KB	Output is correct
16	Correct	55 ms	127828 KB	Output is correct
17	Correct	58 ms	129620 KB	Output is correct
18	Correct	56 ms	127824 KB	Output is correct
19	Correct	59 ms	127824 KB	Output is correct
20	Correct	58 ms	131920 KB	Output is correct
21	Correct	54 ms	127824 KB	Output is correct
22	Correct	56 ms	127828 KB	Output is correct
23	Correct	57 ms	131156 KB	Output is correct
24	Correct	56 ms	131856 KB	Output is correct
25	Correct	55 ms	131772 KB	Output is correct
26	Correct	56 ms	131924 KB	Output is correct
27	Correct	54 ms	131920 KB	Output is correct
28	Correct	58 ms	132436 KB	Output is correct
29	Correct	56 ms	132948 KB	Output is correct
30	Correct	58 ms	131924 KB	Output is correct
31	Correct	66 ms	132468 KB	Output is correct
32	Correct	59 ms	132176 KB	Output is correct
33	Correct	60 ms	133972 KB	Output is correct
34	Correct	62 ms	133968 KB	Output is correct
35	Correct	61 ms	129872 KB	Output is correct
36	Correct	58 ms	128340 KB	Output is correct
37	Correct	63 ms	130576 KB	Output is correct
38	Correct	61 ms	130644 KB	Output is correct
39	Correct	63 ms	130640 KB	Output is correct
40	Correct	64 ms	130556 KB	Output is correct
41	Correct	65 ms	130560 KB	Output is correct
42	Correct	60 ms	129488 KB	Output is correct
43	Correct	63 ms	129484 KB	Output is correct
44	Correct	60 ms	129484 KB	Output is correct
45	Correct	66 ms	135196 KB	Output is correct
46	Correct	66 ms	135196 KB	Output is correct
47	Correct	75 ms	139720 KB	Output is correct
48	Correct	66 ms	128592 KB	Output is correct
49	Correct	72 ms	128456 KB	Output is correct
50	Correct	66 ms	128340 KB	Output is correct
51	Correct	82 ms	138364 KB	Output is correct
52	Correct	83 ms	138988 KB	Output is correct
53	Correct	77 ms	135752 KB	Output is correct
54	Execution timed out	1844 ms	262144 KB	Time limit exceeded
55	Halted	0 ms	0 KB	-

답안 #1084515

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 14.0 / 14.0

Subtask #4 21.0 / 21.0

Subtask #5 0 / 43.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
14.0 / 14.0

Subtask #4
21.0 / 21.0

Subtask #5
0 / 43.0