Submission #68306

#	Time	Username	Problem	Language	Result	Execution time	Memory
68306		zscoder	Ancient Books (IOI17_books)	C++17	100 / 100	280 ms	265840 KiB

books

#include "books.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

map<pair<vi,int>,int> dist;
queue<pair<vi,int> > q; 

void relax(vi &p, int s, int v)
{
	if(dist.find(mp(p,s))==dist.end()) 
	{
		dist[mp(p,s)]=v+1; q.push(mp(p,s));
	}
}

void gen_brute(int n, int s)
{
	vi ori;
	for(int i=0;i<n;i++) ori.pb(i+1);
	dist.clear();
	dist[mp(ori,s)]=0; q.push(mp(ori,s));
	while(!q.empty())
	{
		vi curv=q.front().fi; int curs=q.front().se; int d=dist[mp(curv,curs)]; q.pop();
		if(curs>0) relax(curv,curs-1,d);
		if(curs+1<n) relax(curv,curs+1,d);
		int curhold=0; int B=0;
		for(int i=0;i<n;i++)
		{
			if(curv[i]>0) B^=(1<<(curv[i]-1));
		}
		if(B==(1<<n)-1)
		{
			curhold=curv[curs]-1; curv[curs]=0;
			relax(curv,curs,d-1);
			curv[curs]=curhold+1;
		}
		else
		{
			curhold=31-__builtin_clz(((1<<n)-1)^B);
			curv[curs]=curhold+1;
			relax(curv,curs,d-1);
			curv[curs]=0;
		}
	}
}

int get_naive(vi p, int s)
{
	for(int i=0;i<p.size();i++) p[i]++;
	return dist[mp(p,s)];
}

ll solve(vi p, int s)
{
	//solve for s=0
	int n=p.size();
	int mn=n-1; int mx=0;
	for(int i=0;i<p.size();i++)
	{
		if(p[i]!=i){mn=min(mn,i);mx=max(mx,i);}
	}
	int mxans=0; ll ans=0;
	for(int i=0;i<n;i++) ans+=abs(p[i]-i);
	queue<int> q; q.push(s);
	int curl=s; int curr=s;
	while(1)
	{
		while(!q.empty())
		{
			int u=q.front(); q.pop();
			while(curl>p[u])
			{
				curl--; q.push(curl);
			}
			while(curr<p[u])
			{
				curr++; q.push(curr);
			}
		}
		//after all the free operations
		int distl=0; int distr=0; 
		bool touchr=0; bool touchl=0; //note that if it's useful they'll be touching the same pair
		queue<int> ql,qr;
		int curl2=curl; int curr2=curr;
		while(1)
		{
			if(curl2<=mn) break;
			curl2--; distl++; ql.push(curl2);
			while(!ql.empty())
			{
				int u=ql.front(); ql.pop();
				while(curl2>p[u])
				{
					curl2--; ql.push(curl2);
				}
				if(p[u]>=s) touchr=1;
			}
			if(touchr) break;
		}
		while(1)
		{
			if(curr2>=mx) break;
			curr2++; distr++; qr.push(curr2);
			while(!qr.empty())
			{
				int u=qr.front(); qr.pop();
				while(curr2<p[u])
				{
					curr2++; qr.push(curr2);
				}
				if(p[u]<=s) touchl=1;
			}
			if(touchl) break;
		}
		if(touchl&&touchr)
		{
			mxans+=min(distl,distr);
			while(curl>curl2)
			{
				curl--; q.push(curl);
			}
			while(curr<curr2)
			{
				curr++; q.push(curr);
			}
		}
		else
		{
			mxans+=distl+distr; break;
		}
	}
	return ans+2*mxans;
}

void test(int n, int s)
{
	vi p;
	for(int i=0;i<n;i++) p.pb(i);
	gen_brute(n,s);
	do
	{
		int sum=0;
		for(int i=0;i<p.size();i++) sum+=abs(i-p[i]);
		int ans=get_naive(p,s);
		int res=solve(p,s);
		if(ans!=res)
		{
			cerr<<"WARRRRRRRRRRNING\n";
			for(int v:p)
			{
				cerr<<v<<' ';
			}
			cerr<<'\n';
			cerr<<ans<<' '<<res<<' '<<ans-sum<<'\n';
		}
	}while(next_permutation(p.begin(),p.end()));
}

long long minimum_walk(std::vector<int> p, int s) 
{
	int n=p.size();
	//test(n,s);
	return solve(p,s);
}

Compilation message (stderr)

books.cpp: In function 'int get_naive(vi, int)':
books.cpp:60:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<p.size();i++) p[i]++;
              ~^~~~~~~~~
books.cpp: In function 'll solve(vi, int)':
books.cpp:69:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<p.size();i++)
              ~^~~~~~~~~
books.cpp: In function 'void test(int, int)':
books.cpp:154:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<p.size();i++) sum+=abs(i-p[i]);
               ~^~~~~~~~~
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:172:6: warning: unused variable 'n' [-Wunused-variable]
  int n=p.size();
      ^

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