Submission #67861

#	Time	Username	Problem	Language	Result	Execution time	Memory
67861		zscoder	Ancient Books (IOI17_books)	C++17	50 / 100	296 ms	110192 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)];
}

bool vis[1001111];
ll solve(vi p, int s)
{
	//solve for s=0
	int n=p.size();
	for(int i=0;i<n;i++) vis[i]=0;
	vector<ii> ranges;
	for(int i=0;i<n;i++)
	{
		if(!vis[i])
		{
			int mn=i; int mx=i; vis[i]=1;
			int cur=p[i];
			while(!vis[cur])
			{
				vis[cur]=1; mn=min(mn,cur); mx=max(mx,cur); cur=p[cur];
			}
			if(mn<mx) ranges.pb(mp(mn,mx));
		}
	}
	sort(ranges.begin(),ranges.end());
	int mxans=0;
	ll ans=0;
	for(int i=0;i<n;i++) ans+=abs(p[i]-i);
	int prer=0;
	for(ii range:ranges)
	{
		int l=range.fi; int r=range.se;
		//cerr<<"INTERVAL : "<<l<<' '<<r<<'\n';
		if(l>=prer) mxans+=l-prer;
		prer=max(r,prer);
	}
	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
	{
		for(int v:p)
		{
			cerr<<v<<' ';
		}
		cerr<<'\n';
		int sum=0;
		for(int i=0;i<p.size();i++) sum+=abs(i-p[i]);
		int ans=get_naive(p,s);
		if(ans!=solve(p,s))
		{
			cerr<<"WARRRRRRRRRRNING\n";
			cerr<<ans<<' '<<solve(p,s)<<' '<<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 'void test(int, int)':
books.cpp:112: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:124: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: 0 / 20
• Subtask 5: 0 / 30