Submission #828394

#	Time	Username	Problem	Language	Result	Execution time	Memory
828394		tolbi	Ancient Books (IOI17_books)	C++17	50 / 100	304 ms	24900 KiB

books

#include <bits/stdc++.h>
using namespace std;
#include "books.h"
long long minimum_walk(std::vector<int> p, int s) {
	int n = p.size();
	vector<bool> vis(n,false);
	vector<pair<int,int>> hehe;
	for (int i = 0; i < n; i++){
		if (vis[i]) continue;
		int node = i;
		if (p[node]==node) continue;
		while (!vis[node]){
			vis[node]=true;
			hehe.push_back({min(node,p[node]),1});
			hehe.push_back({max(node,p[node]),-1});
			node=p[node];
		}
	}
	sort(hehe.begin(), hehe.end());
	long long ans = 0;
	int crr = 0;
	int indi = 0;
	for (int i = s; i < n-1; i++){
		while (indi<hehe.size() && hehe[indi].first<=i){
			crr+=hehe[indi].second;
			indi++;
		}
		if (indi!=hehe.size() && crr==0){
			ans+=2;
		}
		if (crr>0) ans+=crr;
	}

	sort(hehe.rbegin(), hehe.rend());
	crr = 0;
	indi = 0;
	for (int i = s; i >= 0; i--){
		while (indi<hehe.size() && hehe[indi].first>=i){
			crr-=hehe[indi].second;
			indi++;
		}
		if (indi!=hehe.size() && crr==0){
			ans+=2;
		}
		if (crr>0) ans+=crr;
	}
	return ans;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:24:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   while (indi<hehe.size() && hehe[indi].first<=i){
      |          ~~~~^~~~~~~~~~~~
books.cpp:28:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   if (indi!=hehe.size() && crr==0){
      |       ~~~~^~~~~~~~~~~~~
books.cpp:38:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   while (indi<hehe.size() && hehe[indi].first>=i){
      |          ~~~~^~~~~~~~~~~~
books.cpp:42:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   if (indi!=hehe.size() && crr==0){
      |       ~~~~^~~~~~~~~~~~~

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