답안 #1084518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1084518	2024-09-06T10:57:15 Z	peacebringer1667	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	131 ms	234420 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 = 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #1084518

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