Submission #298090

#	Time	Username	Problem	Language	Result	Execution time	Memory
298090		TheRedstar	고대 책들 (IOI17_books)	C++11	50 / 100	288 ms	21024 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;
	vector<bool> cfound;
	
	int C=0;//number of cycles
	
	vector<bool> visited(N,false);
	vi cycleof(N,0);
	
	for(int i=0; i<N; i++) {
		if(!visited[i]) {
			//cout << "new cycle from " << i << endl;
			visited[i]=true;
			
			if(p[i]!=i) {
				cmin.push_back(i); //create new cycle
				cmax.push_back(i);
				cfound.push_back(false);
				
				total_distance+=abs(i-p[i]);
				cycleof[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;
					cycleof[current]=C;
				}
				C++;
			} else {
				cycleof[i]=-1;
			}
		}
		
	}
	
	//cout << total_distance <<" for walking with books, cycles: " << C << endl;
	
	int foundc=0;
	
	int ml,mr,l,r; //maxl maxr currentl currentr
	ml=mr=l=r=s;
	
	while(foundc<C) { //not all cycles have been found
		//cout << ml << ' ' << l << ' ' << r << ' ' << mr << ' ' << foundc << endl;
		if(ml>l and mr<r) { //all directly reachable cycles visited
			for(int d=1; d<N; d++) {
				if(mr+d<N and cycleof[mr+d]!=-1 and !cfound[cycleof[mr+d]]) { //found one to the right
					r=mr=mr+d;
					total_distance+=2*d;
					//cout << "walking an extra " << d << " meters (twice) to reach other cycle to the left\n";
					break;
				} else if(ml-d>=0 and cycleof[ml-d]!=-1 and !cfound[cycleof[ml-d]]) { //found one to the left
					l=ml=ml-d;
					total_distance+=2*d;
					//cout << "walking an extra " << d << " meters (twice) to reach other cycle to the right\n";
					break;
				}
			}
		}
		while(ml<=l) { //search for new cycles in reachable range
			int i=l;
			if(cycleof[i]!=-1 and !cfound[cycleof[i]]) {
				cfound[cycleof[i]]=true;
				ml=min(ml,cmin[cycleof[i]]);
				mr=max(mr,cmax[cycleof[i]]);
				foundc++;
				//cout << "found cycle " << cycleof[i] << " at " << i << endl;
			}
			l--;
		}
		while(mr>=r) {
			int i=r;
			if(cycleof[i]!=-1 and !cfound[cycleof[i]]) {
				cfound[cycleof[i]]=true;
				ml=min(ml,cmin[cycleof[i]]);
				mr=max(mr,cmax[cycleof[i]]);
				foundc++;
				//cout << "found cycle " << cycleof[i] << " at " << i << endl;
			}
			r++;
		}
		
		//clock_t start_time = clock(); 
  
    	// looping till required time is not achieved 
    	//while (clock() < start_time + 1000000);
	}
	
	
	
	return total_distance;
}

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