Submission #1035568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035568		ALeonidou	Ancient Books (IOI17_books)	C++17	22 / 100	2087 ms	22628 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define endl "\n"
#define sz(x) (ll)x.size()
#define F first
#define S second
#define pb push_back
#define INF 1000000000000000000

typedef vector <ll> vi;
typedef pair <ll,ll> ii;
typedef vector <ii> vii;

#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;

void printVct(vi &v){
	for (ll i =0; i<sz(v); i++){
		cout<<v[i]<<" ";
	}
	cout<<endl;
}

ll n;

long long minimum_walk(vector<int> P, int ss) {
	n = sz(P);
	vi p(n);
	for (ll i =0; i<n; i++){
		p[i] = P[i];
	}
	ll s = ss;

	ll book = -1, pos = 0;
	ll largestUnsorted = n-1;
	ll ans = 0;
	bool f = true;

	while (largestUnsorted >= 0 && p[largestUnsorted] == largestUnsorted) largestUnsorted--;
	while (largestUnsorted > 0){
		ll startPos = pos;
		// dbg3(startPos, largestUnsorted,ans);
		// printVct(p);
		if (f){		//first time => find book from the start
			while (p[pos] <= pos && pos < n){
				pos++;
			}
			swap(book, p[pos]);
			while (book != largestUnsorted){
				while (p[pos] != largestUnsorted && p[pos] < book && pos < n){
					pos++;
				}
				swap(book, p[pos]);
			}
			f = false;
		}
		else{	//general case => find book from the end
			while (book != largestUnsorted){
				while (p[pos] != largestUnsorted && (p[pos] > book || p[pos] == 0) && pos >= 0){
					pos--;
				}
				swap(book, p[pos]);
			}
			ans += abs(startPos - pos);
			startPos = pos;
		}
		pos = largestUnsorted;
		swap(book, p[pos]);
		ans += abs(pos - startPos);
		while (largestUnsorted >= 0 && p[largestUnsorted] == largestUnsorted) largestUnsorted--;
	}
	ans += pos;

	return ans;
}

/*
4 0
0 2 3 1

4 0
0 1 2 3

4 0
3 2 1 0
*/

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:36:5: warning: unused variable 's' [-Wunused-variable]
   36 |  ll s = ss;
      |     ^

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