답안 #935153

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
935153	2024-02-28T18:02:12 Z	Lobo	고대 책들 (IOI17_books)	C++17	12 / 100	15 ms	58108 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[find(r)]+sol(min(l,dsl[nxr[find(r)]]),dsr[nxr[find(r)]]));
	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--;

	nxr[R] = R;
	costr[R] = 0;
	for(int i = R-1; i >= s; i--) {
		if(find(i) == find(i+1)) {
			continue;
		}
		else if(dsl[find(i+1)] < s or dsr[find(i+1)] == R) {
			nxr[find(i)] = i+1;
			costr[find(i)] = 1;
		}
		else {
			nxr[find(i)] = nxr[find(i+1)];
			costr[find(i)] = costr[find(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

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	57944 KB	Output is correct
2	Correct	12 ms	57948 KB	Output is correct
3	Correct	14 ms	58068 KB	Output is correct
4	Correct	14 ms	57944 KB	Output is correct
5	Correct	12 ms	57948 KB	Output is correct
6	Correct	13 ms	57948 KB	Output is correct
7	Correct	12 ms	57948 KB	Output is correct
8	Correct	13 ms	58068 KB	Output is correct
9	Correct	13 ms	57948 KB	Output is correct
10	Correct	13 ms	57968 KB	Output is correct
11	Correct	13 ms	57996 KB	Output is correct
12	Correct	13 ms	57944 KB	Output is correct
13	Correct	12 ms	57948 KB	Output is correct
14	Correct	12 ms	57988 KB	Output is correct
15	Correct	13 ms	57944 KB	Output is correct
16	Correct	14 ms	57948 KB	Output is correct
17	Correct	13 ms	58052 KB	Output is correct
18	Correct	12 ms	57948 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	57944 KB	Output is correct
2	Correct	12 ms	57948 KB	Output is correct
3	Correct	14 ms	58068 KB	Output is correct
4	Correct	14 ms	57944 KB	Output is correct
5	Correct	12 ms	57948 KB	Output is correct
6	Correct	13 ms	57948 KB	Output is correct
7	Correct	12 ms	57948 KB	Output is correct
8	Correct	13 ms	58068 KB	Output is correct
9	Correct	13 ms	57948 KB	Output is correct
10	Correct	13 ms	57968 KB	Output is correct
11	Correct	13 ms	57996 KB	Output is correct
12	Correct	13 ms	57944 KB	Output is correct
13	Correct	12 ms	57948 KB	Output is correct
14	Correct	12 ms	57988 KB	Output is correct
15	Correct	13 ms	57944 KB	Output is correct
16	Correct	14 ms	57948 KB	Output is correct
17	Correct	13 ms	58052 KB	Output is correct
18	Correct	12 ms	57948 KB	Output is correct
19	Correct	13 ms	57948 KB	Output is correct
20	Correct	13 ms	58020 KB	Output is correct
21	Correct	14 ms	57948 KB	Output is correct
22	Correct	15 ms	57948 KB	Output is correct
23	Correct	13 ms	57948 KB	Output is correct
24	Correct	13 ms	57944 KB	Output is correct
25	Correct	12 ms	57948 KB	Output is correct
26	Correct	13 ms	57948 KB	Output is correct
27	Correct	12 ms	58064 KB	Output is correct
28	Incorrect	13 ms	58072 KB	3rd lines differ - on the 1st token, expected: '44102', found: '1000000000000044090'
29	Halted	0 ms	0 KB	-

Subtask #3
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	57944 KB	Output is correct
2	Correct	12 ms	57948 KB	Output is correct
3	Correct	14 ms	58068 KB	Output is correct
4	Correct	14 ms	57944 KB	Output is correct
5	Correct	12 ms	57948 KB	Output is correct
6	Correct	13 ms	57948 KB	Output is correct
7	Correct	12 ms	57948 KB	Output is correct
8	Correct	13 ms	58068 KB	Output is correct
9	Correct	13 ms	57948 KB	Output is correct
10	Correct	13 ms	57968 KB	Output is correct
11	Correct	13 ms	57996 KB	Output is correct
12	Correct	13 ms	57944 KB	Output is correct
13	Correct	12 ms	57948 KB	Output is correct
14	Correct	12 ms	57988 KB	Output is correct
15	Correct	13 ms	57944 KB	Output is correct
16	Correct	14 ms	57948 KB	Output is correct
17	Correct	13 ms	58052 KB	Output is correct
18	Correct	12 ms	57948 KB	Output is correct
19	Correct	13 ms	57948 KB	Output is correct
20	Correct	13 ms	58020 KB	Output is correct
21	Correct	14 ms	57948 KB	Output is correct
22	Correct	15 ms	57948 KB	Output is correct
23	Correct	13 ms	57948 KB	Output is correct
24	Correct	13 ms	57944 KB	Output is correct
25	Correct	12 ms	57948 KB	Output is correct
26	Correct	13 ms	57948 KB	Output is correct
27	Correct	12 ms	58064 KB	Output is correct
28	Incorrect	13 ms	58072 KB	3rd lines differ - on the 1st token, expected: '44102', found: '1000000000000044090'
29	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	57948 KB	Output is correct
2	Correct	13 ms	57944 KB	Output is correct
3	Correct	13 ms	58108 KB	Output is correct
4	Correct	14 ms	57980 KB	Output is correct
5	Correct	13 ms	57948 KB	Output is correct
6	Incorrect	13 ms	57948 KB	3rd lines differ - on the 1st token, expected: '22140', found: '22144'
7	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	57944 KB	Output is correct
2	Correct	12 ms	57948 KB	Output is correct
3	Correct	14 ms	58068 KB	Output is correct
4	Correct	14 ms	57944 KB	Output is correct
5	Correct	12 ms	57948 KB	Output is correct
6	Correct	13 ms	57948 KB	Output is correct
7	Correct	12 ms	57948 KB	Output is correct
8	Correct	13 ms	58068 KB	Output is correct
9	Correct	13 ms	57948 KB	Output is correct
10	Correct	13 ms	57968 KB	Output is correct
11	Correct	13 ms	57996 KB	Output is correct
12	Correct	13 ms	57944 KB	Output is correct
13	Correct	12 ms	57948 KB	Output is correct
14	Correct	12 ms	57988 KB	Output is correct
15	Correct	13 ms	57944 KB	Output is correct
16	Correct	14 ms	57948 KB	Output is correct
17	Correct	13 ms	58052 KB	Output is correct
18	Correct	12 ms	57948 KB	Output is correct
19	Correct	13 ms	57948 KB	Output is correct
20	Correct	13 ms	58020 KB	Output is correct
21	Correct	14 ms	57948 KB	Output is correct
22	Correct	15 ms	57948 KB	Output is correct
23	Correct	13 ms	57948 KB	Output is correct
24	Correct	13 ms	57944 KB	Output is correct
25	Correct	12 ms	57948 KB	Output is correct
26	Correct	13 ms	57948 KB	Output is correct
27	Correct	12 ms	58064 KB	Output is correct
28	Incorrect	13 ms	58072 KB	3rd lines differ - on the 1st token, expected: '44102', found: '1000000000000044090'
29	Halted	0 ms	0 KB	-

답안 #935153

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