QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#863919#9163. Text editorfryan5 1ms3968kbC++20942b2025-01-20 02:25:462025-01-20 02:25:46

Judging History

你现在查看的是最新测评结果

  • [2025-01-20 02:25:46]
  • 评测
  • 测评结果:5
  • 用时:1ms
  • 内存:3968kb
  • [2025-01-20 02:25:46]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define int long long

const int mxn = 1e6+5;
const int inf = 1e18;

int n,l[mxn],sl,sc,el,ec;
int ans = inf;
queue<array<int,3>> bfs;

map<array<int,2>,int> memo;

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	cin>>n>>sl>>sc>>el>>ec;
	for (int i=1; i<=n; i++) {
		cin>>l[i];
	}
	bfs.push({sl,sc,0});
	while (sz(bfs)) {
		auto [x,y,d] = bfs.front(); bfs.pop();
		y = min(y,l[x]+1);
		if (memo.count({x,y}) && memo[{x,y}] <= d) continue;
		memo[{x,y}] = d;
		if (el==x) {
			ans = min(ans,d+abs(ec-y));
		}
		if (x > 1) {
			//move up
			bfs.push({x-1,y,d+1});
			//move to end of next line
			bfs.push({x-1,l[x-1]+1,d+y});
		}
		if (x < n) {
			//move down
			bfs.push({x+1,y,d+1});
			//move to beginning of line
			bfs.push({x+1,1,l[x]+1-y+d});
		}
	}
	cout<<ans;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 0ms
memory: 3712kb

input:

1
1 1
1 1
0

output:

0

result:

ok single line: '0'

Test #2:

score: 5
Accepted
time: 1ms
memory: 3584kb

input:

2
1 1
1 500000001
1000000000 0

output:

500000000

result:

ok single line: '500000000'

Test #3:

score: 5
Accepted
time: 1ms
memory: 3584kb

input:

2
1 429578866
1 327150572
584071526 0

output:

102428294

result:

ok single line: '102428294'

Test #4:

score: 5
Accepted
time: 0ms
memory: 3584kb

input:

2
2 1
2 1
929403468 0

output:

0

result:

ok single line: '0'

Test #5:

score: 5
Accepted
time: 0ms
memory: 3712kb

input:

2
2 1
2 1
989240738 0

output:

0

result:

ok single line: '0'

Test #6:

score: 5
Accepted
time: 0ms
memory: 3712kb

input:

2
2 1
1 371562870
436620826 0

output:

65057958

result:

ok single line: '65057958'

Test #7:

score: 5
Accepted
time: 0ms
memory: 3712kb

input:

2
1 103853165
1 705401000
836091409 0

output:

130690412

result:

ok single line: '130690412'

Test #8:

score: 5
Accepted
time: 0ms
memory: 3712kb

input:

2
2 1
2 1
924491619 0

output:

0

result:

ok single line: '0'

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 14
Accepted
time: 1ms
memory: 3968kb

input:

952
212 33
98 130
1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 13...

output:

211

result:

ok single line: '211'

Test #10:

score: 14
Accepted
time: 1ms
memory: 3840kb

input:

814
656 144
625 1537
1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642 1642...

output:

280

result:

ok single line: '280'

Test #11:

score: 0
Wrong Answer
time: 1ms
memory: 3712kb

input:

889
197 113
298 10
117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 1...

output:

114

result:

wrong answer 1st lines differ - expected: '115', found: '114'

Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #4:

score: 0
Time Limit Exceeded

Test #43:

score: 0
Time Limit Exceeded

input:

878478
323624 9772968
215921 1051399
227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227...

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%