Submission #283763

#	Time	Username	Problem	Language	Result	Execution time	Memory
283763		erd1	Ancient Books (IOI17_books)	C++14	12 / 100	1 ms	384 KiB

books

#include "books.h"

#include<bits/stdc++.h>

using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef pair<int, int> pii;
typedef long long lld;
typedef long double ld;

template<typename Iter>
ostream& outIt(ostream& out, Iter b, Iter e){
	for(Iter i = b; i != e; ++i)
		out << (i == b?"":" ") << *i;
	return out;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> p){
	return out << '(' << p.ff << ", " << p.ss << ')';
}
template<typename T>
ostream& operator<<(ostream& out, vector<T> v){
	return outIt(out << '[', all(v)) << ']';
}

vector<int> dsu, c;

int root(int i){
	return dsu[i] == i ? i : (dsu[i] = root(dsu[i]));
}
void join(int i, int j){
	dsu[root(i)] = root(j);
}

long long minimum_walk(vector<int> p, int s) {
	lld ans = 0;
	c.resize(0);
	c.resize(p.size()+1);
	for(int i = 0; i < p.size(); i++)if(p[i] != i)ans += abs(p[i]-i), c[min(i, p[i])]++, c[max(i, p[i])+1]--;
	for(int i = 1; i <= p.size(); i++)c[i] += c[i-1];
	for(int i = p.size(), x = 0; i >= 0; i--){
		if(c[i])x = 1;
		else if(x)ans += 2;
	}
	return ans;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i = 0; i < p.size(); i++)if(p[i] != i)ans += abs(p[i]-i), c[min(i, p[i])]++, c[max(i, p[i])+1]--;
      |                 ~~^~~~~~~~~~
books.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i = 1; i <= p.size(); i++)c[i] += c[i-1];
      |                 ~~^~~~~~~~~~~

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