oj.uz

답안 #1064577

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1064577 2024-08-18T14:45:40 Z Dan4Life Text editor (CEOI24_editor) C++17
19 / 100
 524 ms 56764 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a), end(a)
using ll = long long;
using vi = vector<int>;
using ar2 = array<int,2>;
using ar3 = array<int,3>;
using ar4 = array<int,4>;
const int INF = (int)2e9;
const int mxN = (int)1e6+10;
vi v, dis[mxN];
int n, m, xs, ys, xd, yd, nx, ny, L[mxN];
priority_queue<ar3,vector<ar3>,greater<ar3>> pq;

void relax(int x, int y, int w){
	if(dis[nx][ny] > dis[x][y]+w){
		dis[nx][ny] = dis[x][y]+w;
		pq.push({dis[nx][ny],nx,ny});
	}
}

void conv(int &x){ x = lower_bound(all(v),x)-begin(v); }

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> xs >> ys >> xd >> yd;
	L[n+1]=1; v.pb(1); v.pb(ys), v.pb(yd);
	for(int i = 1; i <= n; i++){
		cin >> L[i], L[i]++, v.pb(L[i]);
	}
	for(int i = 1; i <= n+1; i++){
		for(int k = 1; k <= 1000; k++){
			if(L[i]>k) v.pb(L[i]-k);
			v.pb(L[i]+k);
		}
	}
	sort(all(v)); v.erase(unique(all(v)), end(v));
	int m = sz(v);
	for(int i = 0; i <= n+1; i++)
		dis[i].clear(), dis[i].resize(m+1,INF);
	conv(ys); conv(yd); 
	for(int i = 1; i <= n+1; i++) conv(L[i]);
	pq.push({0,xs,ys}); dis[xs][ys]=0;
	while(sz(pq)){
		auto [D,x,y] = pq.top(); pq.pop();
		if(D!=dis[x][y]) continue;
		if(x==xd and y==yd){ cout << D << "\n"; return 0; }
		if(x){
			// go up
			nx = x, ny = y;
			nx--, ny=min(ny,L[nx]), relax(x,y,1);
			// go left
			nx = x, ny = y;
			if(!ny) nx--, ny = L[nx], relax(x,y,1);
		}
		
		if(x!=n+1){ 
			// go down
			nx = x, ny = y;
			nx++, ny=min(ny,L[nx]), relax(x,y,1);
			
			
			// go right
			nx = x, ny = y;
			if(ny==L[nx]) nx++, ny = 0, relax(x,y,1);
		}
		nx = x, ny = y;
		if(y) ny--, relax(x,y,abs(v[ny]-v[y]));
		
		nx = x, ny = y;
		if(ny<L[nx]) ny++, relax(x,y,abs(v[ny]-v[y]));
	}
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 25692 KB Output is correct
2 Correct 7 ms 25692 KB Output is correct

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 25436 KB Output is correct
2 Correct 7 ms 25692 KB Output is correct
3 Correct 7 ms 25640 KB Output is correct
4 Correct 7 ms 25692 KB Output is correct
5 Correct 10 ms 25540 KB Output is correct
6 Correct 7 ms 25528 KB Output is correct
7 Correct 8 ms 25692 KB Output is correct
8 Correct 7 ms 25692 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 25692 KB Output is correct
2 Correct 7 ms 25692 KB Output is correct
3 Correct 7 ms 25436 KB Output is correct
4 Correct 87 ms 41648 KB Output is correct
5 Correct 81 ms 40368 KB Output is correct
6 Correct 42 ms 33240 KB Output is correct
7 Correct 122 ms 41908 KB Output is correct
8 Correct 321 ms 45236 KB Output is correct
9 Correct 396 ms 47296 KB Output is correct
10 Correct 361 ms 47792 KB Output is correct
11 Correct 436 ms 47276 KB Output is correct
12 Correct 372 ms 55220 KB Output is correct
13 Correct 524 ms 54960 KB Output is correct
14 Correct 172 ms 54960 KB Output is correct
15 Correct 105 ms 56500 KB Output is correct
16 Correct 111 ms 56516 KB Output is correct
17 Correct 344 ms 56496 KB Output is correct
18 Correct 297 ms 56656 KB Output is correct
19 Correct 419 ms 56764 KB Output is correct
20 Correct 291 ms 52144 KB Output is correct

Subtask #3
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 25692 KB Output is correct
2 Correct 7 ms 25692 KB Output is correct
3 Correct 7 ms 25436 KB Output is correct
4 Correct 7 ms 25692 KB Output is correct
5 Correct 7 ms 25640 KB Output is correct
6 Correct 7 ms 25692 KB Output is correct
7 Correct 10 ms 25540 KB Output is correct
8 Correct 7 ms 25528 KB Output is correct
9 Correct 8 ms 25692 KB Output is correct
10 Correct 7 ms 25692 KB Output is correct
11 Correct 87 ms 41648 KB Output is correct
12 Correct 81 ms 40368 KB Output is correct
13 Correct 42 ms 33240 KB Output is correct
14 Correct 122 ms 41908 KB Output is correct
15 Correct 321 ms 45236 KB Output is correct
16 Correct 396 ms 47296 KB Output is correct
17 Correct 361 ms 47792 KB Output is correct
18 Correct 436 ms 47276 KB Output is correct
19 Correct 372 ms 55220 KB Output is correct
20 Correct 524 ms 54960 KB Output is correct
21 Correct 172 ms 54960 KB Output is correct
22 Correct 105 ms 56500 KB Output is correct
23 Correct 111 ms 56516 KB Output is correct
24 Correct 344 ms 56496 KB Output is correct
25 Correct 297 ms 56656 KB Output is correct
26 Correct 419 ms 56764 KB Output is correct
27 Correct 291 ms 52144 KB Output is correct
28 Correct 270 ms 41624 KB Output is correct
29 Incorrect 288 ms 43180 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #4
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 25436 KB Output is correct
2 Correct 7 ms 25692 KB Output is correct
3 Correct 7 ms 25640 KB Output is correct
4 Correct 7 ms 25692 KB Output is correct
5 Correct 10 ms 25540 KB Output is correct
6 Correct 7 ms 25528 KB Output is correct
7 Correct 8 ms 25692 KB Output is correct
8 Correct 7 ms 25692 KB Output is correct
9 Correct 87 ms 41648 KB Output is correct
10 Correct 81 ms 40368 KB Output is correct
11 Correct 42 ms 33240 KB Output is correct
12 Correct 122 ms 41908 KB Output is correct
13 Correct 321 ms 45236 KB Output is correct
14 Correct 270 ms 41624 KB Output is correct
15 Incorrect 288 ms 43180 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 25692 KB Output is correct
2 Correct 7 ms 25692 KB Output is correct
3 Correct 7 ms 25436 KB Output is correct
4 Correct 7 ms 25692 KB Output is correct
5 Correct 7 ms 25640 KB Output is correct
6 Correct 7 ms 25692 KB Output is correct
7 Correct 10 ms 25540 KB Output is correct
8 Correct 7 ms 25528 KB Output is correct
9 Correct 8 ms 25692 KB Output is correct
10 Correct 7 ms 25692 KB Output is correct
11 Correct 87 ms 41648 KB Output is correct
12 Correct 81 ms 40368 KB Output is correct
13 Correct 42 ms 33240 KB Output is correct
14 Correct 122 ms 41908 KB Output is correct
15 Correct 321 ms 45236 KB Output is correct
16 Correct 396 ms 47296 KB Output is correct
17 Correct 361 ms 47792 KB Output is correct
18 Correct 436 ms 47276 KB Output is correct
19 Correct 372 ms 55220 KB Output is correct
20 Correct 524 ms 54960 KB Output is correct
21 Correct 172 ms 54960 KB Output is correct
22 Correct 105 ms 56500 KB Output is correct
23 Correct 111 ms 56516 KB Output is correct
24 Correct 344 ms 56496 KB Output is correct
25 Correct 297 ms 56656 KB Output is correct
26 Correct 419 ms 56764 KB Output is correct
27 Correct 291 ms 52144 KB Output is correct
28 Correct 270 ms 41624 KB Output is correct
29 Incorrect 288 ms 43180 KB Output isn't correct
30 Halted 0 ms 0 KB -