제출 #67911

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67911		zscoder	고대 책들 (IOI17_books)	C++17	22 / 100	2089 ms	343316 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];
int sum[1001111];
vector<vi> cycles;
int D[1001111];

int getdist(int s, int e) //get distance from cycle s to cycle e
{
	int l=cycles[s].front(); int r=cycles[s].back();
	int lb=lower_bound(cycles[e].begin(),cycles[e].end(),l)-cycles[e].begin();
	if(lb<cycles[e].size()&&cycles[e][lb]<=r) return 0;
	int mndist = int(1e9); 
	if(lb<cycles[e].size()) mndist=min(mndist,cycles[e][lb]-r);
	lb--;
	if(lb>=0) mndist=min(mndist,l-cycles[e][lb]);
	//cerr<<"GET DIST "<<s<<' '<<e<<' '<<mndist<<'\n';
	return mndist;
}

ll solve(vi p, int s)
{
	//solve for s=0
	int n=p.size();
	for(int i=0;i<n;i++) vis[i]=0;
	cycles.clear();
	cycles.pb({s});
	int excross=0;
	for(int i=0;i<n;i++)
	{
		if(!vis[i])
		{
			vi cycle;
			vis[i]=1; cycle.pb(i);
			int cur=p[i];
			while(!vis[cur])
			{
				cycle.pb(cur); vis[cur]=1; cur=p[cur];
			}
			sort(cycle.begin(),cycle.end());
			if(cycle.size()>=2) 
			{
				if(cycle[0]<=s&&cycle.back()>=s) excross=1;
				cycles.pb(cycle);
			}
		}		
	}
	int mxans=0;
	ll ans=0;
	for(int i=0;i<n;i++) ans+=abs(p[i]-i);
	priority_queue<ii,vector<ii>,greater<ii> > pq;
	for(int i=0;i<cycles.size();i++) D[i]=int(1e9);
	pq.push(mp(0,0)); D[0]=0;
	while(!pq.empty())
	{
		int d=pq.top().fi; int u=pq.top().se; pq.pop();
		if(d>D[u]) continue; 
		mxans=max(mxans,d);
		for(int i=0;i<cycles.size();i++)
		{
			if(i==u) continue;
			int getd=getdist(u,i);
			if(d+getd<D[i])
			{
				D[i]=d+getd;
				pq.push(mp(d+getd,i));
			}
		}
	}
	if(!excross)
	{
		int a[2]={0,0};
		for(int i=1;i<cycles.size();i++)
		{
			if(cycles[i][0]<s) a[0]=max(a[0],D[i]);
			else a[1]=max(a[1],D[i]);
		}
		mxans=a[0]+a[1];
	}
	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);
}

컴파일 시 표준 에러 (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 'int getdist(int, int)':
books.cpp:73:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(lb<cycles[e].size()&&cycles[e][lb]<=r) return 0;
     ~~^~~~~~~~~~~~~~~~~
books.cpp:75:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(lb<cycles[e].size()) mndist=min(mndist,cycles[e][lb]-r);
     ~~^~~~~~~~~~~~~~~~~
books.cpp: In function 'll solve(vi, int)':
books.cpp:113:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<cycles.size();i++) D[i]=int(1e9);
              ~^~~~~~~~~~~~~~
books.cpp:120:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<cycles.size();i++)
               ~^~~~~~~~~~~~~~
books.cpp:134:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<cycles.size();i++)
               ~^~~~~~~~~~~~~~
books.cpp: In function 'void test(int, int)':
books.cpp:157: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:169:6: warning: unused variable 'n' [-Wunused-variable]
  int n=p.size();
      ^

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