Submission #145415

#	Time	Username	Problem	Language	Result	Execution time	Memory
145415		mohammedehab2002	Ancient Books (IOI17_books)	C++11	12 / 100	14 ms	5116 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> p;
vector<pair<int,int> > c,d;
pair<int,int> dp[1005][1005];
bool vis[1005],calc[1005][1005];
int cyc[1005],dist[1005][1005];
void dfs(int i)
{
	vis[i]=1;
	auto &x=c[c.size()-1];
	x.first=min(x.first,i);
	x.second=max(x.second,i);
	cyc[i]=c.size()-1;
	if (!vis[p[i]])
	dfs(p[i]);
}
pair<int,int> Union(pair<int,int> a,pair<int,int> b)
{
	return {min(a.first,b.first),max(a.second,b.second)};
}
pair<int,int> solve(int l,int r)
{
	if (calc[l][r])
	return dp[l][r];
	if (l==r)
	return c[cyc[l]];
	calc[l][r]=1;
	return dp[l][r]=Union(solve(l,r-1),solve(r,r));
}
long long minimum_walk(vector<int> pp,int s)
{
	p=pp;
	while (!p.empty() && p.back()+1==p.size())
	p.pop_back();
	int n=p.size();
	if (!n)
	return 0;
	long long ans=0;
	for (int i=0;i<n;i++)
	{
		ans+=abs(p[i]-i);
		if (!vis[i])
		{
			c.push_back({i,i});
			dfs(i);
		}
	}
	queue<pair<int,int> > q;
	q.push(solve(s,s));
	while (!q.empty())
	{
		auto cp=q.front();
		q.pop();
		if (cp.first)
		{
			auto np=solve(cp.first-1,cp.second);
			if (!dist[np.first][np.second])
			{
				dist[np.first][np.second]=dist[cp.first][cp.second]+1;
				q.push(np);
			}
		}
		if (cp.second!=n-1)
		{
			auto np=solve(cp.first,cp.second+1);
			if (!dist[np.first][np.second])
			{
				dist[np.first][np.second]=dist[cp.first][cp.second]+1;
				q.push(np);
			}
		}
	}
	return ans+2*dist[0][n-1];
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:35:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (!p.empty() && p.back()+1==p.size())
                       ~~~~~~~~~~^~~~~~~~~~

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