Submission #139476

#	Time	Username	Problem	Language	Result	Execution time	Memory
139476		Kenzo_1114	Ancient Books (IOI17_books)	C++14	0 / 100	2 ms	376 KiB

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;
const int MAXN=1000010;

int marc[MAXN],sub[MAXN],cur;
long long int dist,resp;
vector<int> grafo;

void dfs(int v)
{
	marc[v]=1;

	int viz=grafo[v];

	if(marc[viz]==1)
	{
		dist+=abs(v-viz);
		return;
	}

	dist+=abs(v-viz);
	dfs(viz);
}

long long int  minimum_walk(vector<int> p,int s)
{
	vector<pair<int,int> > cycle;
	grafo=p;

	for(int i=p.size()-1;i>=0;i--)
	{
		if(i!=p[i])	break;
		p.pop_back();
	}

	for(int i=0;i<p.size();i++)
	{
		int ini=i,	fim=p[i];

		while(i<fim)
		{
			i++;
			fim=max(fim,p[i]);
		}

		cycle.push_back(make_pair(ini,fim));
	}

	for(int i=0;i<cycle.size();i++)
	{
		for(int j=cycle[i].first;j<=cycle[i].second;j++)
		{
			if(marc[j]==1)	continue;
			dist=0;
			dfs(j);
			resp+=dist;
		}
		if(i!=cycle.size()-1)	resp+=2*(cycle[i].first-cycle[i].second);
	}

	return resp;
}

/*
int main ()
{
	int N,S,val;
	vector<int> P;

	scanf("%d %d",&N,&S);

	for(int i=0;i<N;i++)	
		scanf("%d",&val),	P.push_back(val);

	printf("%lld\n",minimum_walk(P,S));
}
*/

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<p.size();i++)
              ~^~~~~~~~~
books.cpp:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<cycle.size();i++)
              ~^~~~~~~~~~~~~
books.cpp:59:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i!=cycle.size()-1) resp+=2*(cycle[i].first-cycle[i].second);
      ~^~~~~~~~~~~~~~~~

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