답안 #51060 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51060	2018-06-15T22:26:00 Z	FLDutchman	고대 책들 (IOI17_books)	C++14	50 / 100	499 ms	151044 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;
bitset<NMAX> vis;
vi point;

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

// 
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)};
}

long long minimum_walk(std::vector<int> p, int s) {
	vis.reset();
	N = p.size();
	FOR(i, 0, N) point.pb(p[i]);
	FOR(i, 0, N) if(!vis[i]) flood(i, numCycles++);
	FOR(i, 0, numCycles) sort(cycles[i].begin(), cycles[i].end());
	//cout << "Preprocessed" << endl;
	//ii k = bounds(2, 1);
	//cout << k.fst << " " << k.snd << endl;
	//Find segments:
	vii segs;
	ll rm = 0;
	ll lm = 0;
	//cout << "numCycles: " << numCycles << endl;
	FOR(i, 0, numCycles){
		//cout << lm << " " << rm << endl;
		if(cycles[i].size() == 1) continue;
		if(rm <= cycles[i][0]) {
			if(rm - lm > 1) segs.pb({lm, rm});
			lm = cycles[i][0]; rm = cycles[i].back()+1;
		}
		rm = max(rm, cycles[i].back()+1);
	}

	if(rm - lm > 1) segs.pb({lm, rm});

	//cout << segs.size() << endl;
	ll dist = 0;
	if(segs.size() > 0)
		dist  = segs[0].fst*2;
	//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) );
	}
	//cout << "sfdf" << endl;
	return dist;
}
/*
3 1
0 2 1

4 0
0 1 3 2

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

10 0
0 1 4 5 2 3 7 6 9 8
*/

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23928 KB	Output is correct
2	Correct	21 ms	24040 KB	Output is correct
3	Correct	20 ms	24040 KB	Output is correct
4	Correct	23 ms	24040 KB	Output is correct
5	Correct	21 ms	24100 KB	Output is correct
6	Correct	21 ms	24120 KB	Output is correct
7	Correct	22 ms	24124 KB	Output is correct
8	Correct	21 ms	24128 KB	Output is correct
9	Correct	23 ms	24144 KB	Output is correct
10	Correct	21 ms	24144 KB	Output is correct
11	Correct	25 ms	24316 KB	Output is correct
12	Correct	24 ms	24316 KB	Output is correct
13	Correct	22 ms	24316 KB	Output is correct
14	Correct	22 ms	24316 KB	Output is correct
15	Correct	22 ms	24316 KB	Output is correct
16	Correct	23 ms	24316 KB	Output is correct
17	Correct	22 ms	24316 KB	Output is correct
18	Correct	26 ms	24316 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23928 KB	Output is correct
2	Correct	21 ms	24040 KB	Output is correct
3	Correct	20 ms	24040 KB	Output is correct
4	Correct	23 ms	24040 KB	Output is correct
5	Correct	21 ms	24100 KB	Output is correct
6	Correct	21 ms	24120 KB	Output is correct
7	Correct	22 ms	24124 KB	Output is correct
8	Correct	21 ms	24128 KB	Output is correct
9	Correct	23 ms	24144 KB	Output is correct
10	Correct	21 ms	24144 KB	Output is correct
11	Correct	25 ms	24316 KB	Output is correct
12	Correct	24 ms	24316 KB	Output is correct
13	Correct	22 ms	24316 KB	Output is correct
14	Correct	22 ms	24316 KB	Output is correct
15	Correct	22 ms	24316 KB	Output is correct
16	Correct	23 ms	24316 KB	Output is correct
17	Correct	22 ms	24316 KB	Output is correct
18	Correct	26 ms	24316 KB	Output is correct
19	Correct	21 ms	24316 KB	Output is correct
20	Correct	21 ms	24316 KB	Output is correct
21	Correct	23 ms	24316 KB	Output is correct
22	Correct	22 ms	24316 KB	Output is correct
23	Correct	21 ms	24316 KB	Output is correct
24	Correct	23 ms	24316 KB	Output is correct
25	Correct	21 ms	24316 KB	Output is correct
26	Correct	23 ms	24316 KB	Output is correct
27	Correct	24 ms	24316 KB	Output is correct
28	Correct	26 ms	24316 KB	Output is correct
29	Correct	23 ms	24316 KB	Output is correct

Subtask #3
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23928 KB	Output is correct
2	Correct	21 ms	24040 KB	Output is correct
3	Correct	20 ms	24040 KB	Output is correct
4	Correct	23 ms	24040 KB	Output is correct
5	Correct	21 ms	24100 KB	Output is correct
6	Correct	21 ms	24120 KB	Output is correct
7	Correct	22 ms	24124 KB	Output is correct
8	Correct	21 ms	24128 KB	Output is correct
9	Correct	23 ms	24144 KB	Output is correct
10	Correct	21 ms	24144 KB	Output is correct
11	Correct	25 ms	24316 KB	Output is correct
12	Correct	24 ms	24316 KB	Output is correct
13	Correct	22 ms	24316 KB	Output is correct
14	Correct	22 ms	24316 KB	Output is correct
15	Correct	22 ms	24316 KB	Output is correct
16	Correct	23 ms	24316 KB	Output is correct
17	Correct	22 ms	24316 KB	Output is correct
18	Correct	26 ms	24316 KB	Output is correct
19	Correct	21 ms	24316 KB	Output is correct
20	Correct	21 ms	24316 KB	Output is correct
21	Correct	23 ms	24316 KB	Output is correct
22	Correct	22 ms	24316 KB	Output is correct
23	Correct	21 ms	24316 KB	Output is correct
24	Correct	23 ms	24316 KB	Output is correct
25	Correct	21 ms	24316 KB	Output is correct
26	Correct	23 ms	24316 KB	Output is correct
27	Correct	24 ms	24316 KB	Output is correct
28	Correct	26 ms	24316 KB	Output is correct
29	Correct	23 ms	24316 KB	Output is correct
30	Correct	492 ms	74196 KB	Output is correct
31	Correct	499 ms	74196 KB	Output is correct
32	Correct	266 ms	84816 KB	Output is correct
33	Correct	264 ms	90196 KB	Output is correct
34	Correct	374 ms	96920 KB	Output is correct
35	Correct	261 ms	100600 KB	Output is correct
36	Correct	246 ms	100600 KB	Output is correct
37	Correct	243 ms	100600 KB	Output is correct
38	Correct	254 ms	104968 KB	Output is correct
39	Correct	267 ms	111352 KB	Output is correct
40	Correct	280 ms	117832 KB	Output is correct
41	Correct	371 ms	134952 KB	Output is correct
42	Correct	336 ms	135168 KB	Output is correct
43	Correct	285 ms	151044 KB	Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23928 KB	Output is correct
2	Correct	21 ms	24040 KB	Output is correct
3	Correct	20 ms	24040 KB	Output is correct
4	Correct	23 ms	24040 KB	Output is correct
5	Correct	21 ms	24100 KB	Output is correct
6	Correct	21 ms	24120 KB	Output is correct
7	Correct	22 ms	24124 KB	Output is correct
8	Correct	21 ms	24128 KB	Output is correct
9	Correct	23 ms	24144 KB	Output is correct
10	Correct	21 ms	24144 KB	Output is correct
11	Correct	25 ms	24316 KB	Output is correct
12	Correct	24 ms	24316 KB	Output is correct
13	Correct	22 ms	24316 KB	Output is correct
14	Correct	22 ms	24316 KB	Output is correct
15	Correct	22 ms	24316 KB	Output is correct
16	Correct	23 ms	24316 KB	Output is correct
17	Correct	22 ms	24316 KB	Output is correct
18	Correct	26 ms	24316 KB	Output is correct
19	Correct	21 ms	24316 KB	Output is correct
20	Correct	21 ms	24316 KB	Output is correct
21	Correct	23 ms	24316 KB	Output is correct
22	Correct	22 ms	24316 KB	Output is correct
23	Correct	21 ms	24316 KB	Output is correct
24	Correct	23 ms	24316 KB	Output is correct
25	Correct	21 ms	24316 KB	Output is correct
26	Correct	23 ms	24316 KB	Output is correct
27	Correct	24 ms	24316 KB	Output is correct
28	Correct	26 ms	24316 KB	Output is correct
29	Correct	23 ms	24316 KB	Output is correct
30	Correct	492 ms	74196 KB	Output is correct
31	Correct	499 ms	74196 KB	Output is correct
32	Correct	266 ms	84816 KB	Output is correct
33	Correct	264 ms	90196 KB	Output is correct
34	Correct	374 ms	96920 KB	Output is correct
35	Correct	261 ms	100600 KB	Output is correct
36	Correct	246 ms	100600 KB	Output is correct
37	Correct	243 ms	100600 KB	Output is correct
38	Correct	254 ms	104968 KB	Output is correct
39	Correct	267 ms	111352 KB	Output is correct
40	Correct	280 ms	117832 KB	Output is correct
41	Correct	371 ms	134952 KB	Output is correct
42	Correct	336 ms	135168 KB	Output is correct
43	Correct	285 ms	151044 KB	Output is correct
44	Incorrect	21 ms	151044 KB	3rd lines differ - on the 1st token, expected: '3304', found: '2744'
45	Halted	0 ms	0 KB	-

답안 #51060

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