답안 #51062 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51062	2018-06-16T01:46:48 Z	FLDutchman	고대 책들 (IOI17_books)	C++14	50 / 100	484 ms	94552 KB

books

#include "books.h"
#include "bits/stdc++.h"
using namespace std;

#define pb push_back
#define fst first
#define snd second
#define FOR(i, l, r) for(int i = l; i < r; i++)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;

const ll NMAX = 1e6 + 10;
const ll INF = 1e9;

vi cycles[NMAX];
ll numCycles, N, S;
vi vis;
vi point;

void flood(ll n, ll c){
	//cout << "Flood " << n << " " << c << endl;
	cycles[c].pb(n);
	ll k = point[n];
	vis[n] = c;
	if(vis[k] == -1) flood(k, c); 
}

ii bounds[NMAX];
// 
/*ii bounds(ll p, ll c){
	//cout << p << endl;
	auto &cy = cycles[c];	
	if(cy[0] > p) return {-1, cy[0]};
	if(cy.back() <= p) return {cy.back(), INF};
	auto x = lower_bound(cycles[c].begin(), cycles[c].end(), p);
	return {*x, *(++x)};
}*/

ll f(ll lbound, ll rbound){
	//cout << "f" << endl;
	rbound --;
	ii &k = bounds[vis[lbound]];
	ll lgoal = k.fst, rgoal = k.snd;
	//cout << lgoal << " " << rgoal << endl;
	ll l = lbound, r = rbound;
	while(l < lgoal || r > rgoal){
		//cout << l << " " << r << endl;
		ll t;
		if(l >= lgoal) t = r--;
		else t = l++;
		ii &k = bounds[vis[t]];
		lgoal = max(lgoal, k.fst);
		rgoal = min(rgoal, k.snd);
	}
	//cout << "goals " << lgoal << " " << rgoal << endl;
	if(lgoal == S) return 0;
	ll li = S, ri = S+1;
	ll lm = lgoal, rm = lgoal;

	ll c1 = 0;
	FOR(i, lgoal+1, S){
		ll a = cycles[vis[i]][0], b = cycles[vis[i]].back()+1;
		if(a != i) continue;
		if(b > S) {
			li = i;
			break;
		} 
		if(rm <= i){
			if(rm - lm > 1) c1 += lm - rm;
			lm = i;
		}
		rm = max(rm, b);
	}
	c1 += li - lgoal;

	// closed interval
	lm = rgoal-1; rm = rgoal-1;
	ll c2 = 0;
	for(int i = rgoal-1; i > S; i--){
		ll a = cycles[vis[i]][0], b = cycles[vis[i]].back();
		if(b != i) continue;
		if(a <= S){
			ri = i+1;
			break;
		}
		if(i < lm){
			if(rm - lm > 1) c2 += lm - (rm + 1);
			rm = i;
		}
		lm = min(lm, a);
	}
	c2 += rgoal+1 - ri;
	// Interval covering 
	//cout << "cover " <<  li << " " << ri << endl;
	//cout << "c1 c2: " << c1 << " " << c2 << endl;
	ll res = f(li, ri) + min(c1, c2);


	return res;	
}

long long minimum_walk(std::vector<int> p, int s) {
	vis.assign(p.size(), -1);
	N = p.size();
	S = s;
	FOR(i, 0, N) point.pb(p[i]);
	FOR(i, 0, N) if(vis[i] == -1) flood(i, numCycles++);
	FOR(i, 0, numCycles) sort(cycles[i].begin(), cycles[i].end());
	FOR(c, 0, numCycles) {
		auto &cy = cycles[c];	
		if(cy[0] > s) bounds[c] = {-1, cy[0]};
		else if(cy.back() <= s) bounds[c] = {cy.back(), INF};
		else {
			auto x = upper_bound(cycles[c].begin(), cycles[c].end(), s);
			bounds[c] = {*(x-1), *(x)};
		}
		//cout << c << ": " << bounds[c].fst << " " << bounds[c].snd << endl;
	}

	//cout << "Preprocessed" << endl;
	//ii k = bounds(2, 1);
	//cout << k.fst << " " << k.snd << endl;
	//Find segments:
	vii segs;
	ll rm = 0;
	ll lm = 0;
	ll l = -1, r = -1;
	//cout << "numCycles: " << numCycles << endl;
	//FOR(i, 0, numCycles) {
		//for(int k : cycles[i]) cout << k << " ";
		//cout << endl;
	//}
	FOR(i, 0, numCycles){
		if(cycles[i].size() == 1) continue;
		if(rm <= cycles[i][0]) {
			if(rm - lm > 1) segs.pb({lm, rm});
			if(lm <= S and S < rm) l = lm, r = rm;
			lm = cycles[i][0]; rm = cycles[i].back()+1;
		}
		rm = max(rm, cycles[i].back()+1);
		//cout << lm << " " << rm << " " << i << endl;
	}
	//cout <<l << " " << r << endl;
	if(rm - lm > 1) segs.pb({lm, rm});
	if(lm <= S and S < rm) l = lm, r = rm;
	//cout << numCycles << endl;

	//cout << segs.size() << endl;
	ll dist = 0;
	//cout << dist << endl;
	FOR(i, 0, N) dist += abs(i - p[i]);
	//cout << dist << endl;
	//cout << segs.size() - 1 << endl;
	//FOR(i, 0, (ll)segs.size()) cout << segs[i].fst << " " << segs[i].snd << endl;
	FOR(i, 0, (ll)segs.size()-1){
		dist += 2*(segs[i+1].fst - (segs[i].snd-1) );
	}
	if(segs.size() > 0){
		if(segs[0].fst > S) dist += 2 * (segs[0].fst - S);
		if(segs.back().snd <= S) dist += 2*(S - segs.back().snd+1);
	}
	
	//cout << "sfdf" << endl;
	if(l != -1) dist += 2*f(l, r);
	return dist;
}
/*
3 1
0 2 1

4 0
0 1 3 2

4 1
2 3 0 1
4 0
0 1 2 3

10 4
0 1 4 5 2 3 7 6 9 8
10 4
0 6 4 5 2 3 7 1 9 8
10 4
0 6 2 5 4 3 7 1 9 8
(24)
10 0
0 6 2 5 4 3 7 1 9 8
(22)
11 3
10 9 2 3 6 7 4 5 8 1 0
(50)
*/

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	23800 KB	Output is correct
2	Correct	23 ms	23908 KB	Output is correct
3	Correct	22 ms	23908 KB	Output is correct
4	Correct	22 ms	23908 KB	Output is correct
5	Correct	21 ms	23944 KB	Output is correct
6	Correct	20 ms	24024 KB	Output is correct
7	Correct	22 ms	24096 KB	Output is correct
8	Correct	26 ms	24116 KB	Output is correct
9	Correct	24 ms	24116 KB	Output is correct
10	Correct	22 ms	24116 KB	Output is correct
11	Correct	20 ms	24116 KB	Output is correct
12	Correct	21 ms	24116 KB	Output is correct
13	Correct	21 ms	24116 KB	Output is correct
14	Correct	21 ms	24116 KB	Output is correct
15	Correct	22 ms	24116 KB	Output is correct
16	Correct	29 ms	24116 KB	Output is correct
17	Correct	25 ms	24188 KB	Output is correct
18	Correct	22 ms	24188 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	23800 KB	Output is correct
2	Correct	23 ms	23908 KB	Output is correct
3	Correct	22 ms	23908 KB	Output is correct
4	Correct	22 ms	23908 KB	Output is correct
5	Correct	21 ms	23944 KB	Output is correct
6	Correct	20 ms	24024 KB	Output is correct
7	Correct	22 ms	24096 KB	Output is correct
8	Correct	26 ms	24116 KB	Output is correct
9	Correct	24 ms	24116 KB	Output is correct
10	Correct	22 ms	24116 KB	Output is correct
11	Correct	20 ms	24116 KB	Output is correct
12	Correct	21 ms	24116 KB	Output is correct
13	Correct	21 ms	24116 KB	Output is correct
14	Correct	21 ms	24116 KB	Output is correct
15	Correct	22 ms	24116 KB	Output is correct
16	Correct	29 ms	24116 KB	Output is correct
17	Correct	25 ms	24188 KB	Output is correct
18	Correct	22 ms	24188 KB	Output is correct
19	Correct	23 ms	24188 KB	Output is correct
20	Correct	22 ms	24188 KB	Output is correct
21	Correct	22 ms	24188 KB	Output is correct
22	Correct	20 ms	24188 KB	Output is correct
23	Correct	23 ms	24188 KB	Output is correct
24	Correct	21 ms	24188 KB	Output is correct
25	Correct	25 ms	24188 KB	Output is correct
26	Correct	21 ms	24188 KB	Output is correct
27	Correct	23 ms	24188 KB	Output is correct
28	Correct	22 ms	24188 KB	Output is correct
29	Correct	24 ms	24188 KB	Output is correct

Subtask #3
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	23800 KB	Output is correct
2	Correct	23 ms	23908 KB	Output is correct
3	Correct	22 ms	23908 KB	Output is correct
4	Correct	22 ms	23908 KB	Output is correct
5	Correct	21 ms	23944 KB	Output is correct
6	Correct	20 ms	24024 KB	Output is correct
7	Correct	22 ms	24096 KB	Output is correct
8	Correct	26 ms	24116 KB	Output is correct
9	Correct	24 ms	24116 KB	Output is correct
10	Correct	22 ms	24116 KB	Output is correct
11	Correct	20 ms	24116 KB	Output is correct
12	Correct	21 ms	24116 KB	Output is correct
13	Correct	21 ms	24116 KB	Output is correct
14	Correct	21 ms	24116 KB	Output is correct
15	Correct	22 ms	24116 KB	Output is correct
16	Correct	29 ms	24116 KB	Output is correct
17	Correct	25 ms	24188 KB	Output is correct
18	Correct	22 ms	24188 KB	Output is correct
19	Correct	23 ms	24188 KB	Output is correct
20	Correct	22 ms	24188 KB	Output is correct
21	Correct	22 ms	24188 KB	Output is correct
22	Correct	20 ms	24188 KB	Output is correct
23	Correct	23 ms	24188 KB	Output is correct
24	Correct	21 ms	24188 KB	Output is correct
25	Correct	25 ms	24188 KB	Output is correct
26	Correct	21 ms	24188 KB	Output is correct
27	Correct	23 ms	24188 KB	Output is correct
28	Correct	22 ms	24188 KB	Output is correct
29	Correct	24 ms	24188 KB	Output is correct
30	Correct	484 ms	81736 KB	Output is correct
31	Correct	462 ms	81736 KB	Output is correct
32	Correct	269 ms	94552 KB	Output is correct
33	Correct	281 ms	94552 KB	Output is correct
34	Correct	370 ms	94552 KB	Output is correct
35	Correct	295 ms	94552 KB	Output is correct
36	Correct	274 ms	94552 KB	Output is correct
37	Correct	247 ms	94552 KB	Output is correct
38	Correct	277 ms	94552 KB	Output is correct
39	Correct	276 ms	94552 KB	Output is correct
40	Correct	296 ms	94552 KB	Output is correct
41	Correct	364 ms	94552 KB	Output is correct
42	Correct	331 ms	94552 KB	Output is correct
43	Correct	318 ms	94552 KB	Output is correct

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	21 ms	94552 KB	3rd lines differ - on the 1st token, expected: '3304', found: '3152'
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	23800 KB	Output is correct
2	Correct	23 ms	23908 KB	Output is correct
3	Correct	22 ms	23908 KB	Output is correct
4	Correct	22 ms	23908 KB	Output is correct
5	Correct	21 ms	23944 KB	Output is correct
6	Correct	20 ms	24024 KB	Output is correct
7	Correct	22 ms	24096 KB	Output is correct
8	Correct	26 ms	24116 KB	Output is correct
9	Correct	24 ms	24116 KB	Output is correct
10	Correct	22 ms	24116 KB	Output is correct
11	Correct	20 ms	24116 KB	Output is correct
12	Correct	21 ms	24116 KB	Output is correct
13	Correct	21 ms	24116 KB	Output is correct
14	Correct	21 ms	24116 KB	Output is correct
15	Correct	22 ms	24116 KB	Output is correct
16	Correct	29 ms	24116 KB	Output is correct
17	Correct	25 ms	24188 KB	Output is correct
18	Correct	22 ms	24188 KB	Output is correct
19	Correct	23 ms	24188 KB	Output is correct
20	Correct	22 ms	24188 KB	Output is correct
21	Correct	22 ms	24188 KB	Output is correct
22	Correct	20 ms	24188 KB	Output is correct
23	Correct	23 ms	24188 KB	Output is correct
24	Correct	21 ms	24188 KB	Output is correct
25	Correct	25 ms	24188 KB	Output is correct
26	Correct	21 ms	24188 KB	Output is correct
27	Correct	23 ms	24188 KB	Output is correct
28	Correct	22 ms	24188 KB	Output is correct
29	Correct	24 ms	24188 KB	Output is correct
30	Correct	484 ms	81736 KB	Output is correct
31	Correct	462 ms	81736 KB	Output is correct
32	Correct	269 ms	94552 KB	Output is correct
33	Correct	281 ms	94552 KB	Output is correct
34	Correct	370 ms	94552 KB	Output is correct
35	Correct	295 ms	94552 KB	Output is correct
36	Correct	274 ms	94552 KB	Output is correct
37	Correct	247 ms	94552 KB	Output is correct
38	Correct	277 ms	94552 KB	Output is correct
39	Correct	276 ms	94552 KB	Output is correct
40	Correct	296 ms	94552 KB	Output is correct
41	Correct	364 ms	94552 KB	Output is correct
42	Correct	331 ms	94552 KB	Output is correct
43	Correct	318 ms	94552 KB	Output is correct
44	Incorrect	21 ms	94552 KB	3rd lines differ - on the 1st token, expected: '3304', found: '3152'
45	Halted	0 ms	0 KB	-

답안 #51062

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 28.0 / 28.0

Subtask #4 0 / 20.0

Subtask #5 0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
10.0 / 10.0

Subtask #3
28.0 / 28.0

Subtask #4
0 / 20.0

Subtask #5
0 / 30.0