oj.uz

Submission #139476

# Submission time Handle Problem Language Result Execution time Memory
139476 2019-07-31T20:37:05 Z Kenzo_1114 Ancient Books (IOI17_books) C++14
0 / 100
 2 ms 376 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB 3rd lines differ - on the 1st token, expected: '3304', found: '2744'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -