Submission #821309

#	Time	Username	Problem	Language	Result	Execution time	Memory
821309		vjudge1	Ancient Books (IOI17_books)	C++17	0 / 100	1 ms	468 KiB

books

#include "books.h"
#include<bits/stdc++.h>

using namespace std;


long long minimum_walk(vector<int> p, int s) {
	int n = (int)p.size();
	bool us[n] = {};
	vector<vector<int>> cmps;
	int sum = 0;
	for(int i = 0; i < n; i++) {
		sum += abs(p[i] - i);
		if(us[i]) continue;
		int x = i;
		cmps.push_back({});
		while(!us[x]) {
			us[x] = 1;
			cmps.back().push_back(x);
			x = p[x];
		}
	}	
	if((int)cmps.size() == 1) 
		return sum;
	if(n == 2) 
		return 0;
	
	if(n == 3) {
		int l = 0;
		while(l < n && p[l] == l) l++;
		return sum + 2 * l;
	}
	if(n == 4) {
		if((int)cmps.size() == 4) 
			return 0;
		if((int)cmps.size() == 3) {
			int l = 0;
			while(l < n && p[l] == l) l++;
			return sum + 2 * l;
		}
		if((int)cmps.size() == 1) 
			return sum;
		int mx = 0;
		for(auto v : cmps) 
			mx = max(mx, (int)v.size());
		if(mx > 2) {
			int l = 0;
			while(l < n && p[l] == l) l++;
			return sum + 2 * l;
		}
		if(cmps[0].back() < cmps[1][0]) 
			return sum + 2;
		return sum + 1;
	}
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:10:22: warning: control reaches end of non-void function [-Wreturn-type]
   10 |  vector<vector<int>> cmps;
      |                      ^~~~

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