답안 #72758 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72758	2018-08-26T22:37:46 Z	FLDutchman	고대 책들 (IOI17_books)	C++14	12 / 100	4 ms	816 KB

books

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

typedef int INT;

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

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

int N;
vi p;
vi color;
vii interval;
vii segments;


void expand(int &l, int &r){
	//cout << "expanding " << l << " " << r << endl; 
	int gl = l-1, gr = r+1;
	while(l != gl || r != gr){
		//cout << l << " " << r << endl;
		//cout << gl << " " << gr << endl;
		if(l != gl) {l--; gl = min(gl, interval[color[l]].fst); gr = max(gr, interval[color[l]].snd);}
		if(r != gr) {r++; gl = min(gl, interval[color[r]].fst); gr = max(gr, interval[color[r]].snd);}
	}
	//cout << l << " " << r << endl;
}

long long minimum_walk(std::vector<INT> P, INT s) {
	FOR(i, 0, P.size()) p.pb(P[i]);
	N = p.size();
	color.assign(N, -1);
	int c = 0;
	FOR(i, 0, N) if(color[i] == -1){
		int j = i;
		int l = i, r = i;
		while(color[j]  == -1){
			color[j] = c;
			j = p[j];
			r = max(j, r);
			l = min(j, r);
		}			
		interval.pb({l, r});
		c++;

	}
	if(interval.size() == 0) return 0;
	//cout << "colors\n";
	//for(int c : color) cout<<c<<" ";
	//cout<<endl;
	//for(ii p : interval) cout << p.fst << " " << p.snd << endl;
	int k = 0;
	while(interval[k].fst == interval[k].snd) k++;
	if(k == interval.size()) return 0;
	int l = interval[k].fst, r = interval[k].snd;
	for(ii inter : interval) if(inter.fst != inter.snd){
		if(r < inter.fst) {
			segments.pb({l, r});
			l = inter.fst, r = inter.snd;
		} else r = max(r, inter.snd);	
	}

	//cout << "intervals\n";
	//FOR(i, 0, N) cout << interval[color[i]].fst << " " << interval[color[i]].snd << endl;
	segments.pb({l, r});
	int res = 0;
	FOR(i, 1, segments.size()){
		res += 2*(segments[i].fst - segments[i-1].snd);
	}

	for(auto seg : segments) if(seg.fst <= s and s <= seg.snd){
		int l = s+1, r = s-1;
		res -= 2;
		while(l != seg.fst or r != seg.snd){
			expand(l, r);
			res += 2;
		}
	}
	//cout<<res<<endl;
	//for(ii p : segments) cout << p.fst << " " << p.snd << endl;
	if(s < segments[0].fst) res += 2*(segments[0].fst-s);
	if(s > segments.back().snd) res += 2*(s - segments.back().snd);
	FOR(i, 0, N) res += abs(i-p[i]);
	return res;
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, INT)':
books.cpp:9:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,l,r) for(int i = (l); i < (r); i++)
                                       ^
books.cpp:37:2: note: in expansion of macro 'FOR'
  FOR(i, 0, P.size()) p.pb(P[i]);
  ^~~
books.cpp:61:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(k == interval.size()) return 0;
     ~~^~~~~~~~~~~~~~~~~~
books.cpp:9:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,l,r) for(int i = (l); i < (r); i++)
                                       ^
books.cpp:74:2: note: in expansion of macro 'FOR'
  FOR(i, 1, segments.size()){
  ^~~

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	252 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	392 KB	Output is correct
4	Correct	2 ms	408 KB	Output is correct
5	Correct	2 ms	408 KB	Output is correct
6	Correct	2 ms	464 KB	Output is correct
7	Correct	3 ms	540 KB	Output is correct
8	Correct	3 ms	540 KB	Output is correct
9	Correct	2 ms	540 KB	Output is correct
10	Correct	4 ms	540 KB	Output is correct
11	Correct	2 ms	540 KB	Output is correct
12	Correct	3 ms	540 KB	Output is correct
13	Correct	2 ms	540 KB	Output is correct
14	Correct	2 ms	540 KB	Output is correct
15	Correct	3 ms	540 KB	Output is correct
16	Correct	2 ms	604 KB	Output is correct
17	Correct	2 ms	604 KB	Output is correct
18	Correct	3 ms	604 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	252 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	392 KB	Output is correct
4	Correct	2 ms	408 KB	Output is correct
5	Correct	2 ms	408 KB	Output is correct
6	Correct	2 ms	464 KB	Output is correct
7	Correct	3 ms	540 KB	Output is correct
8	Correct	3 ms	540 KB	Output is correct
9	Correct	2 ms	540 KB	Output is correct
10	Correct	4 ms	540 KB	Output is correct
11	Correct	2 ms	540 KB	Output is correct
12	Correct	3 ms	540 KB	Output is correct
13	Correct	2 ms	540 KB	Output is correct
14	Correct	2 ms	540 KB	Output is correct
15	Correct	3 ms	540 KB	Output is correct
16	Correct	2 ms	604 KB	Output is correct
17	Correct	2 ms	604 KB	Output is correct
18	Correct	3 ms	604 KB	Output is correct
19	Correct	3 ms	612 KB	Output is correct
20	Correct	3 ms	612 KB	Output is correct
21	Runtime error	3 ms	744 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Halted	0 ms	0 KB	-

Subtask #3
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	252 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	392 KB	Output is correct
4	Correct	2 ms	408 KB	Output is correct
5	Correct	2 ms	408 KB	Output is correct
6	Correct	2 ms	464 KB	Output is correct
7	Correct	3 ms	540 KB	Output is correct
8	Correct	3 ms	540 KB	Output is correct
9	Correct	2 ms	540 KB	Output is correct
10	Correct	4 ms	540 KB	Output is correct
11	Correct	2 ms	540 KB	Output is correct
12	Correct	3 ms	540 KB	Output is correct
13	Correct	2 ms	540 KB	Output is correct
14	Correct	2 ms	540 KB	Output is correct
15	Correct	3 ms	540 KB	Output is correct
16	Correct	2 ms	604 KB	Output is correct
17	Correct	2 ms	604 KB	Output is correct
18	Correct	3 ms	604 KB	Output is correct
19	Correct	3 ms	612 KB	Output is correct
20	Correct	3 ms	612 KB	Output is correct
21	Runtime error	3 ms	744 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	792 KB	Output is correct
2	Correct	3 ms	792 KB	Output is correct
3	Correct	2 ms	800 KB	Output is correct
4	Correct	3 ms	800 KB	Output is correct
5	Correct	3 ms	800 KB	Output is correct
6	Correct	2 ms	800 KB	Output is correct
7	Correct	3 ms	816 KB	Output is correct
8	Correct	2 ms	816 KB	Output is correct
9	Correct	2 ms	816 KB	Output is correct
10	Runtime error	3 ms	816 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	252 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	392 KB	Output is correct
4	Correct	2 ms	408 KB	Output is correct
5	Correct	2 ms	408 KB	Output is correct
6	Correct	2 ms	464 KB	Output is correct
7	Correct	3 ms	540 KB	Output is correct
8	Correct	3 ms	540 KB	Output is correct
9	Correct	2 ms	540 KB	Output is correct
10	Correct	4 ms	540 KB	Output is correct
11	Correct	2 ms	540 KB	Output is correct
12	Correct	3 ms	540 KB	Output is correct
13	Correct	2 ms	540 KB	Output is correct
14	Correct	2 ms	540 KB	Output is correct
15	Correct	3 ms	540 KB	Output is correct
16	Correct	2 ms	604 KB	Output is correct
17	Correct	2 ms	604 KB	Output is correct
18	Correct	3 ms	604 KB	Output is correct
19	Correct	3 ms	612 KB	Output is correct
20	Correct	3 ms	612 KB	Output is correct
21	Runtime error	3 ms	744 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Halted	0 ms	0 KB	-

답안 #72758

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