답안 #1084519

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1084519	2024-09-06T11:01:09 Z	peacebringer1667	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	118 ms	234320 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 + 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);
	
	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	43 ms	111452 KB	Output is correct
2	Correct	42 ms	111440 KB	Output is correct
3	Correct	46 ms	111452 KB	Output is correct
4	Correct	45 ms	111632 KB	Output is correct
5	Correct	43 ms	111440 KB	Output is correct
6	Correct	43 ms	111636 KB	Output is correct
7	Correct	45 ms	111640 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	111612 KB	Output is correct
2	Correct	42 ms	111448 KB	Output is correct
3	Correct	43 ms	111440 KB	Output is correct
4	Correct	43 ms	111536 KB	Output is correct
5	Correct	44 ms	111440 KB	Output is correct
6	Correct	43 ms	111440 KB	Output is correct
7	Correct	46 ms	111516 KB	Output is correct
8	Correct	46 ms	111672 KB	Output is correct
9	Correct	44 ms	111696 KB	Output is correct
10	Correct	43 ms	111700 KB	Output is correct
11	Correct	43 ms	111704 KB	Output is correct
12	Correct	48 ms	111696 KB	Output is correct
13	Correct	48 ms	111700 KB	Output is correct
14	Correct	43 ms	111952 KB	Output is correct
15	Correct	43 ms	111956 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	111452 KB	Output is correct
2	Correct	48 ms	111444 KB	Output is correct
3	Correct	46 ms	111440 KB	Output is correct
4	Correct	50 ms	111440 KB	Output is correct
5	Correct	43 ms	111440 KB	Output is correct
6	Correct	43 ms	111452 KB	Output is correct
7	Correct	43 ms	111576 KB	Output is correct
8	Correct	49 ms	111640 KB	Output is correct
9	Correct	43 ms	111704 KB	Output is correct
10	Correct	46 ms	111616 KB	Output is correct
11	Correct	48 ms	111696 KB	Output is correct
12	Correct	48 ms	111724 KB	Output is correct
13	Correct	49 ms	111776 KB	Output is correct
14	Correct	47 ms	111900 KB	Output is correct
15	Correct	44 ms	111952 KB	Output is correct
16	Correct	48 ms	111444 KB	Output is correct
17	Correct	45 ms	113240 KB	Output is correct
18	Correct	49 ms	111444 KB	Output is correct
19	Correct	45 ms	111708 KB	Output is correct
20	Correct	44 ms	115540 KB	Output is correct
21	Correct	45 ms	111440 KB	Output is correct
22	Correct	44 ms	111444 KB	Output is correct
23	Correct	45 ms	114828 KB	Output is correct
24	Correct	63 ms	115588 KB	Output is correct
25	Correct	69 ms	115676 KB	Output is correct
26	Correct	47 ms	115796 KB	Output is correct
27	Correct	48 ms	116064 KB	Output is correct
28	Correct	47 ms	116048 KB	Output is correct
29	Correct	47 ms	116564 KB	Output is correct
30	Correct	46 ms	116048 KB	Output is correct
31	Correct	46 ms	116052 KB	Output is correct
32	Correct	47 ms	116048 KB	Output is correct
33	Correct	48 ms	117572 KB	Output is correct
34	Correct	48 ms	117584 KB	Output is correct

Subtask #4
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	48 ms	111440 KB	Output is correct
2	Correct	52 ms	111444 KB	Output is correct
3	Correct	48 ms	111544 KB	Output is correct
4	Correct	44 ms	111452 KB	Output is correct
5	Correct	48 ms	111452 KB	Output is correct
6	Correct	49 ms	111444 KB	Output is correct
7	Correct	44 ms	111444 KB	Output is correct
8	Correct	50 ms	111700 KB	Output is correct
9	Correct	47 ms	111700 KB	Output is correct
10	Correct	45 ms	111744 KB	Output is correct
11	Correct	48 ms	111704 KB	Output is correct
12	Correct	49 ms	111700 KB	Output is correct
13	Correct	47 ms	111696 KB	Output is correct
14	Correct	48 ms	111808 KB	Output is correct
15	Correct	49 ms	111956 KB	Output is correct
16	Correct	47 ms	111452 KB	Output is correct
17	Correct	49 ms	113284 KB	Output is correct
18	Correct	50 ms	111708 KB	Output is correct
19	Correct	49 ms	111700 KB	Output is correct
20	Correct	55 ms	115792 KB	Output is correct
21	Correct	48 ms	111444 KB	Output is correct
22	Correct	48 ms	111440 KB	Output is correct
23	Correct	46 ms	114768 KB	Output is correct
24	Correct	53 ms	115536 KB	Output is correct
25	Correct	47 ms	115752 KB	Output is correct
26	Correct	46 ms	115676 KB	Output is correct
27	Correct	46 ms	115796 KB	Output is correct
28	Correct	47 ms	116052 KB	Output is correct
29	Correct	49 ms	116564 KB	Output is correct
30	Correct	47 ms	115796 KB	Output is correct
31	Correct	51 ms	116048 KB	Output is correct
32	Correct	46 ms	116052 KB	Output is correct
33	Correct	49 ms	117584 KB	Output is correct
34	Correct	50 ms	117584 KB	Output is correct
35	Correct	54 ms	113484 KB	Output is correct
36	Correct	46 ms	111964 KB	Output is correct
37	Correct	50 ms	114288 KB	Output is correct
38	Correct	50 ms	114116 KB	Output is correct
39	Correct	59 ms	114280 KB	Output is correct
40	Correct	55 ms	114376 KB	Output is correct
41	Correct	51 ms	114260 KB	Output is correct
42	Correct	48 ms	113244 KB	Output is correct
43	Correct	48 ms	113104 KB	Output is correct
44	Correct	48 ms	113076 KB	Output is correct
45	Correct	57 ms	118516 KB	Output is correct
46	Correct	59 ms	118632 KB	Output is correct

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	111460 KB	Output is correct
2	Correct	43 ms	111584 KB	Output is correct
3	Correct	47 ms	111448 KB	Output is correct
4	Correct	50 ms	111396 KB	Output is correct
5	Correct	44 ms	111440 KB	Output is correct
6	Correct	48 ms	111444 KB	Output is correct
7	Correct	46 ms	111584 KB	Output is correct
8	Correct	44 ms	111708 KB	Output is correct
9	Correct	49 ms	111700 KB	Output is correct
10	Correct	47 ms	111700 KB	Output is correct
11	Correct	45 ms	111964 KB	Output is correct
12	Correct	45 ms	111788 KB	Output is correct
13	Correct	43 ms	111880 KB	Output is correct
14	Correct	44 ms	111956 KB	Output is correct
15	Correct	47 ms	111952 KB	Output is correct
16	Correct	43 ms	111444 KB	Output is correct
17	Correct	45 ms	113232 KB	Output is correct
18	Correct	50 ms	111444 KB	Output is correct
19	Correct	44 ms	111700 KB	Output is correct
20	Correct	54 ms	115536 KB	Output is correct
21	Correct	44 ms	111452 KB	Output is correct
22	Correct	50 ms	111452 KB	Output is correct
23	Correct	45 ms	114776 KB	Output is correct
24	Correct	47 ms	115512 KB	Output is correct
25	Correct	46 ms	115544 KB	Output is correct
26	Correct	52 ms	115804 KB	Output is correct
27	Correct	49 ms	115792 KB	Output is correct
28	Correct	49 ms	116048 KB	Output is correct
29	Correct	48 ms	116560 KB	Output is correct
30	Correct	46 ms	115952 KB	Output is correct
31	Correct	50 ms	116156 KB	Output is correct
32	Correct	45 ms	116060 KB	Output is correct
33	Correct	52 ms	117592 KB	Output is correct
34	Correct	49 ms	117584 KB	Output is correct
35	Correct	49 ms	113428 KB	Output is correct
36	Correct	45 ms	112020 KB	Output is correct
37	Correct	50 ms	114240 KB	Output is correct
38	Correct	52 ms	114336 KB	Output is correct
39	Correct	50 ms	114404 KB	Output is correct
40	Correct	55 ms	114216 KB	Output is correct
41	Correct	53 ms	114260 KB	Output is correct
42	Correct	48 ms	113104 KB	Output is correct
43	Correct	48 ms	113100 KB	Output is correct
44	Correct	52 ms	113100 KB	Output is correct
45	Correct	55 ms	118516 KB	Output is correct
46	Correct	55 ms	118500 KB	Output is correct
47	Correct	64 ms	123212 KB	Output is correct
48	Correct	59 ms	112464 KB	Output is correct
49	Correct	54 ms	112464 KB	Output is correct
50	Correct	59 ms	112216 KB	Output is correct
51	Correct	71 ms	121616 KB	Output is correct
52	Correct	72 ms	121784 KB	Output is correct
53	Correct	61 ms	118868 KB	Output is correct
54	Runtime error	118 ms	234320 KB	Execution killed with signal 11
55	Halted	0 ms	0 KB	-

답안 #1084519

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