Submission #51055

#	Time	Username	Problem	Language	Result	Execution time	Memory
51055		FLDutchman	Ancient Books (IOI17_books)	C++14	0 / 100	22 ms	24364 KiB

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){
	//cerr << "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){
	//cerr << p << endl;
	auto &cy = cycles[c];	
	if(cy[0] > p) return {-1, cy[0]};
	if(cy[cy.size()-1] <= p) return {cy[cy.size()-1], 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;
	FOR(i, 0, numCycles){
		//cout << lm << " " << rm << endl;
		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 = segs[0].fst*2;
	FOR(i, 0, N) dist += abs(i - p[i]);
	FOR(i, 0, segs.size()-1){
		dist += 2*(segs[i+1].fst - segs[i].snd);
	}

	return dist;
}
/*
3 1
0 2 1
*/

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:8: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:69:6:
  FOR(i, 0, segs.size()-1){
      ~~~~~~~~~~~~~~~~~~~               
books.cpp:69:2: note: in expansion of macro 'FOR'
  FOR(i, 0, segs.size()-1){
  ^~~

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