| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 145414 | mohammedehab2002 | 고대 책들 (IOI17_books) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "books.h"
#include "grader.cpp"
#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];
}