Submission #935141

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
935141	2024-02-28T17:47:17 Z	Lobo	Ancient Books (IOI17_books)	C++17	12 / 100	18 ms	58060 KB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 1e6+10;

int n;
int ds[maxn], dsz[maxn], dsl[maxn], dsr[maxn];
int nxr[maxn], costr[maxn];

int find(int v) {
	if(v == ds[v]) return v;
	return ds[v] = find(ds[v]);
}

void join(int u, int v) {
	u = find(u);
	v = find(v);
	if(u == v) return;

	if(dsz[u] < dsz[v]) swap(u,v);
	dsz[u]+= dsz[v];
	dsl[u] = min(dsl[u],dsl[v]);
	dsr[u] = max(dsr[u],dsr[v]);
	ds[v] = u;
}

int L,R;
map<int,int> dp[maxn];
int sol(int l, int r) {
	if(dp[l].count(r)) return dp[l][r];
	if(l == L && r == R) return dp[l][r] = 0;

	dp[l][r] = inf;
	if(l > L) dp[l][r] = min(dp[l][r],2+sol(dsl[find(l-1)],max(r,dsr[find(l-1)])));
	if(r < R) dp[l][r] = min(dp[l][r],2*costr[r+1]+sol(min(l,dsl[find(nxr[r+1])]),dsr[find(nxr[r+1])]));
	return dp[l][r];
}

long long minimum_walk(vector<int32_t> p, int32_t s) {
	// return 0;

	n = p.size();

	for(int i = 0; i < n; i++) {
		ds[i] = i;
		dsz[i] = 1;
		dsl[i] = i;
		dsr[i] = i;
	}

	for(int i = 0; i < n; i++) {
		join(i,p[i]);
	}

	int itl = s;
	while(itl != n) {
		int itr = itl;
		int cur = itl;
		while(cur <= itr) {
			itr = max(itr,dsr[find(cur)]);
			cur++;
		}
		for(int i = itl; i < itr; i++) {
			join(i,i+1);
		}
		itl = itr+1;
	}

	int itr = s;
	while(itr >= 0) {
		int itl = itr;
		int cur = itr;
		while(cur >= itl) {
			itl = min(itl,dsl[find(cur)]);
			cur--;
		}
		for(int i = itl; i < itr; i++) {
			join(i,i+1);
		}
		itr = itl-1;
	}

	L = 0;
	R = n-1;
	while(L < s && dsz[find(L)] == 1) L++;
	while(R > s && dsz[find(R)] == 1) R--;

	for(int i = R-1; i >= s; i--) {
		if(dsl[find(i+1)] < s or dsr[find(i+1)] == R) {
			nxr[i] = i+1;
			costr[i] = 1;
		}
		else {
			nxr[i] = nxr[i+1];
			costr[i] = costr[i+1]+1;
		}
	}

	int ans = 0;
	for(int i = 0; i < n; i++) ans+= abs(p[i]-i);

	return ans+sol(dsl[find(s)],dsr[find(s)]);
}

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	57944 KB	Output is correct
2	Correct	13 ms	57948 KB	Output is correct
3	Correct	13 ms	57944 KB	Output is correct
4	Correct	12 ms	57944 KB	Output is correct
5	Correct	13 ms	57944 KB	Output is correct
6	Correct	12 ms	57948 KB	Output is correct
7	Correct	12 ms	57948 KB	Output is correct
8	Correct	12 ms	57948 KB	Output is correct
9	Correct	12 ms	56020 KB	Output is correct
10	Correct	12 ms	57948 KB	Output is correct
11	Correct	12 ms	55896 KB	Output is correct
12	Correct	14 ms	57948 KB	Output is correct
13	Correct	12 ms	57948 KB	Output is correct
14	Correct	12 ms	55900 KB	Output is correct
15	Correct	12 ms	57972 KB	Output is correct
16	Correct	13 ms	58060 KB	Output is correct
17	Correct	13 ms	58008 KB	Output is correct
18	Correct	13 ms	57948 KB	Output is correct

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	57944 KB	Output is correct
2	Correct	13 ms	57948 KB	Output is correct
3	Correct	13 ms	57944 KB	Output is correct
4	Correct	12 ms	57944 KB	Output is correct
5	Correct	13 ms	57944 KB	Output is correct
6	Correct	12 ms	57948 KB	Output is correct
7	Correct	12 ms	57948 KB	Output is correct
8	Correct	12 ms	57948 KB	Output is correct
9	Correct	12 ms	56020 KB	Output is correct
10	Correct	12 ms	57948 KB	Output is correct
11	Correct	12 ms	55896 KB	Output is correct
12	Correct	14 ms	57948 KB	Output is correct
13	Correct	12 ms	57948 KB	Output is correct
14	Correct	12 ms	55900 KB	Output is correct
15	Correct	12 ms	57972 KB	Output is correct
16	Correct	13 ms	58060 KB	Output is correct
17	Correct	13 ms	58008 KB	Output is correct
18	Correct	13 ms	57948 KB	Output is correct
19	Correct	12 ms	57944 KB	Output is correct
20	Correct	13 ms	57944 KB	Output is correct
21	Correct	12 ms	55900 KB	Output is correct
22	Incorrect	13 ms	57948 KB	3rd lines differ - on the 1st token, expected: '2082', found: '2778'
23	Halted	0 ms	0 KB	-

Subtask #3
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	57944 KB	Output is correct
2	Correct	13 ms	57948 KB	Output is correct
3	Correct	13 ms	57944 KB	Output is correct
4	Correct	12 ms	57944 KB	Output is correct
5	Correct	13 ms	57944 KB	Output is correct
6	Correct	12 ms	57948 KB	Output is correct
7	Correct	12 ms	57948 KB	Output is correct
8	Correct	12 ms	57948 KB	Output is correct
9	Correct	12 ms	56020 KB	Output is correct
10	Correct	12 ms	57948 KB	Output is correct
11	Correct	12 ms	55896 KB	Output is correct
12	Correct	14 ms	57948 KB	Output is correct
13	Correct	12 ms	57948 KB	Output is correct
14	Correct	12 ms	55900 KB	Output is correct
15	Correct	12 ms	57972 KB	Output is correct
16	Correct	13 ms	58060 KB	Output is correct
17	Correct	13 ms	58008 KB	Output is correct
18	Correct	13 ms	57948 KB	Output is correct
19	Correct	12 ms	57944 KB	Output is correct
20	Correct	13 ms	57944 KB	Output is correct
21	Correct	12 ms	55900 KB	Output is correct
22	Incorrect	13 ms	57948 KB	3rd lines differ - on the 1st token, expected: '2082', found: '2778'
23	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	57948 KB	Output is correct
2	Correct	13 ms	57948 KB	Output is correct
3	Correct	13 ms	57948 KB	Output is correct
4	Incorrect	14 ms	57944 KB	3rd lines differ - on the 1st token, expected: '2094', found: '2368'
5	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	57944 KB	Output is correct
2	Correct	13 ms	57948 KB	Output is correct
3	Correct	13 ms	57944 KB	Output is correct
4	Correct	12 ms	57944 KB	Output is correct
5	Correct	13 ms	57944 KB	Output is correct
6	Correct	12 ms	57948 KB	Output is correct
7	Correct	12 ms	57948 KB	Output is correct
8	Correct	12 ms	57948 KB	Output is correct
9	Correct	12 ms	56020 KB	Output is correct
10	Correct	12 ms	57948 KB	Output is correct
11	Correct	12 ms	55896 KB	Output is correct
12	Correct	14 ms	57948 KB	Output is correct
13	Correct	12 ms	57948 KB	Output is correct
14	Correct	12 ms	55900 KB	Output is correct
15	Correct	12 ms	57972 KB	Output is correct
16	Correct	13 ms	58060 KB	Output is correct
17	Correct	13 ms	58008 KB	Output is correct
18	Correct	13 ms	57948 KB	Output is correct
19	Correct	12 ms	57944 KB	Output is correct
20	Correct	13 ms	57944 KB	Output is correct
21	Correct	12 ms	55900 KB	Output is correct
22	Incorrect	13 ms	57948 KB	3rd lines differ - on the 1st token, expected: '2082', found: '2778'
23	Halted	0 ms	0 KB	-

Submission #935141

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 0 / 10.0

Subtask #3 0 / 28.0

Subtask #4 0 / 20.0

Subtask #5 0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
0 / 10.0

Subtask #3
0 / 28.0

Subtask #4
0 / 20.0

Subtask #5
0 / 30.0