Submission #297227

#	Time	Username	Problem	Language	Result	Execution time	Memory
297227		TheRedstar	고대 책들 (IOI17_books)	C++11	50 / 100	250 ms	25936 KiB

books

#include "books.h"

#include <bits/stdc++.h>


using namespace std;
typedef vector<int> vi;


long long minimum_walk(vi p, int s) {
	int N=p.size();
	
	long long total_distance=0;

	vi cmin; //cycle min and max positions
	vi cmax;
	
	int C=0;//number of cycles
	
	vector<bool> visited(N,false);
	
	for(int i=0; i<N; i++) {
		if(!visited[i]) {
			//cout << "new cycle from " << i << endl;
			visited[i]=true;
			
			cmin.push_back(i); //create new cycle
			cmax.push_back(i);
			
			total_distance+=abs(i-p[i]);
			
			for(int current=p[i]; current!=i; current=p[current]) { //add other points
				cmin[C]=min(cmin[C],current);
				cmax[C]=max(cmax[C],current);
				
				total_distance+=abs(current-p[current]);
				
				visited[current]=true;
			}
			C++;
		}
		
	}
	
	//cout << total_distance <<" for walking with books, cycles: " << C << endl;
	
	vector<pair<int,bool>> events={{s,0},{s,1}}; //0 for start, 1 for end
	for(int c=0; c<C; c++) {
		if(cmin[c]!=cmax[c]) {
			events.push_back({cmin[c],0});
			events.push_back({cmax[c],1});
		}
	}
	
	sort(events.begin(),events.end());
	
	
	int active_c=0;
	for(int e=0; e<events.size(); e++) {
		if(get<1>(events[e])==false) {//new
			active_c++;
		} else {//remove
			active_c--;
			if(active_c==0 and e<events.size()-1) {//there is a next event which needs to be walked to
				total_distance+=2*(events[e+1].first-events[e].first);
			}
		}
	
	
	}
	
	return total_distance;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(vi, int)':
books.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int e=0; e<events.size(); e++) {
      |               ~^~~~~~~~~~~~~~
books.cpp:64:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |    if(active_c==0 and e<events.size()-1) {//there is a next event which needs to be walked to
      |                       ~^~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30