답안 #51057 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51057	2018-06-15T22:05:46 Z	FLDutchman	고대 책들 (IOI17_books)	C++14	12 / 100	23 ms	24400 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 vector<int> vi;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;

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

vi cycles[NMAX];
int numCycles, N;
bitset<NMAX> vis;
vi point;

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

// 
ii bounds(int p, int 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();
	point = p;
	N = p.size();
	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;
	int rm = 0;
	int 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());
	}

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

	//cout << segs.size() << endl;
	int dist = 0;
	if(segs.size() > 0)
		dist  = segs[0].fst*2;
	FOR(i, 0, N) dist += abs(i - p[i]);
	//cout << dist << endl;
	//cout << segs.size() - 1 << endl;
	FOR(i, 0, (int)segs.size()-1){
		dist += 2*(segs[i+1].fst - segs[i].snd);
	}
	//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
*/

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	23928 KB	Output is correct
2	Correct	21 ms	23928 KB	Output is correct
3	Correct	21 ms	24116 KB	Output is correct
4	Correct	21 ms	24172 KB	Output is correct
5	Correct	20 ms	24172 KB	Output is correct
6	Correct	21 ms	24172 KB	Output is correct
7	Correct	22 ms	24228 KB	Output is correct
8	Correct	20 ms	24272 KB	Output is correct
9	Correct	21 ms	24272 KB	Output is correct
10	Correct	21 ms	24272 KB	Output is correct
11	Correct	23 ms	24336 KB	Output is correct
12	Correct	21 ms	24336 KB	Output is correct
13	Correct	21 ms	24336 KB	Output is correct
14	Correct	21 ms	24336 KB	Output is correct
15	Correct	21 ms	24400 KB	Output is correct
16	Correct	21 ms	24400 KB	Output is correct
17	Correct	21 ms	24400 KB	Output is correct
18	Correct	21 ms	24400 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	23928 KB	Output is correct
2	Correct	21 ms	23928 KB	Output is correct
3	Correct	21 ms	24116 KB	Output is correct
4	Correct	21 ms	24172 KB	Output is correct
5	Correct	20 ms	24172 KB	Output is correct
6	Correct	21 ms	24172 KB	Output is correct
7	Correct	22 ms	24228 KB	Output is correct
8	Correct	20 ms	24272 KB	Output is correct
9	Correct	21 ms	24272 KB	Output is correct
10	Correct	21 ms	24272 KB	Output is correct
11	Correct	23 ms	24336 KB	Output is correct
12	Correct	21 ms	24336 KB	Output is correct
13	Correct	21 ms	24336 KB	Output is correct
14	Correct	21 ms	24336 KB	Output is correct
15	Correct	21 ms	24400 KB	Output is correct
16	Correct	21 ms	24400 KB	Output is correct
17	Correct	21 ms	24400 KB	Output is correct
18	Correct	21 ms	24400 KB	Output is correct
19	Correct	21 ms	24400 KB	Output is correct
20	Correct	21 ms	24400 KB	Output is correct
21	Correct	23 ms	24400 KB	Output is correct
22	Incorrect	21 ms	24400 KB	3rd lines differ - on the 1st token, expected: '2082', found: '1764'
23	Halted	0 ms	0 KB	-

Subtask #3
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	23928 KB	Output is correct
2	Correct	21 ms	23928 KB	Output is correct
3	Correct	21 ms	24116 KB	Output is correct
4	Correct	21 ms	24172 KB	Output is correct
5	Correct	20 ms	24172 KB	Output is correct
6	Correct	21 ms	24172 KB	Output is correct
7	Correct	22 ms	24228 KB	Output is correct
8	Correct	20 ms	24272 KB	Output is correct
9	Correct	21 ms	24272 KB	Output is correct
10	Correct	21 ms	24272 KB	Output is correct
11	Correct	23 ms	24336 KB	Output is correct
12	Correct	21 ms	24336 KB	Output is correct
13	Correct	21 ms	24336 KB	Output is correct
14	Correct	21 ms	24336 KB	Output is correct
15	Correct	21 ms	24400 KB	Output is correct
16	Correct	21 ms	24400 KB	Output is correct
17	Correct	21 ms	24400 KB	Output is correct
18	Correct	21 ms	24400 KB	Output is correct
19	Correct	21 ms	24400 KB	Output is correct
20	Correct	21 ms	24400 KB	Output is correct
21	Correct	23 ms	24400 KB	Output is correct
22	Incorrect	21 ms	24400 KB	3rd lines differ - on the 1st token, expected: '2082', found: '1764'
23	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	23 ms	24400 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	20 ms	23928 KB	Output is correct
2	Correct	21 ms	23928 KB	Output is correct
3	Correct	21 ms	24116 KB	Output is correct
4	Correct	21 ms	24172 KB	Output is correct
5	Correct	20 ms	24172 KB	Output is correct
6	Correct	21 ms	24172 KB	Output is correct
7	Correct	22 ms	24228 KB	Output is correct
8	Correct	20 ms	24272 KB	Output is correct
9	Correct	21 ms	24272 KB	Output is correct
10	Correct	21 ms	24272 KB	Output is correct
11	Correct	23 ms	24336 KB	Output is correct
12	Correct	21 ms	24336 KB	Output is correct
13	Correct	21 ms	24336 KB	Output is correct
14	Correct	21 ms	24336 KB	Output is correct
15	Correct	21 ms	24400 KB	Output is correct
16	Correct	21 ms	24400 KB	Output is correct
17	Correct	21 ms	24400 KB	Output is correct
18	Correct	21 ms	24400 KB	Output is correct
19	Correct	21 ms	24400 KB	Output is correct
20	Correct	21 ms	24400 KB	Output is correct
21	Correct	23 ms	24400 KB	Output is correct
22	Incorrect	21 ms	24400 KB	3rd lines differ - on the 1st token, expected: '2082', found: '1764'
23	Halted	0 ms	0 KB	-

답안 #51057

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