Submission #297240

#	Time	Username	Problem	Language	Result	Execution time	Memory
297240		TheRedstar	Ancient Books (IOI17_books)	C++11	50 / 100	243 ms	24276 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);
	vi incycle(N,0);
	
	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]);
			incycle[i]=C;
			
			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;
				incycle[current]=C;
			}
			C++;
		}
		
	}
	
	//cout << total_distance <<" for walking with books, cycles: " << C << endl;
	
	//edge case: s on correct table
	
	if(cmin[incycle[s]]==cmax[incycle[s]]) {
		//cout << "initial move needed\n";
		for(int d=1; d<N; d++) {
			if(s-d >=0 and cmin[incycle[s-d]]!=cmax[incycle[s-d]]) {
				total_distance+=2*d;
				break;
			}
			if(s+d < N and cmin[incycle[s+d]]!=cmax[incycle[s+d]]) {
				total_distance+=2*d;
				break;
			}
		}
	}
	
	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:78: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]
   78 |  for(int e=0; e<events.size(); e++) {
      |               ~^~~~~~~~~~~~~~
books.cpp:83: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]
   83 |    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