답안 #67911 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67911	2018-08-15T13:38:35 Z	zscoder	고대 책들 (IOI17_books)	C++17	22 / 100	2000 ms	343316 KB

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);
}

Compilation message

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.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	4 ms	492 KB	Output is correct
3	Correct	2 ms	532 KB	Output is correct
4	Correct	3 ms	532 KB	Output is correct
5	Correct	2 ms	556 KB	Output is correct
6	Correct	2 ms	636 KB	Output is correct
7	Correct	3 ms	640 KB	Output is correct
8	Correct	2 ms	640 KB	Output is correct
9	Correct	2 ms	640 KB	Output is correct
10	Correct	3 ms	652 KB	Output is correct
11	Correct	3 ms	656 KB	Output is correct
12	Correct	2 ms	656 KB	Output is correct
13	Correct	3 ms	664 KB	Output is correct
14	Correct	3 ms	672 KB	Output is correct
15	Correct	2 ms	672 KB	Output is correct
16	Correct	3 ms	672 KB	Output is correct
17	Correct	3 ms	684 KB	Output is correct
18	Correct	3 ms	688 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	4 ms	492 KB	Output is correct
3	Correct	2 ms	532 KB	Output is correct
4	Correct	3 ms	532 KB	Output is correct
5	Correct	2 ms	556 KB	Output is correct
6	Correct	2 ms	636 KB	Output is correct
7	Correct	3 ms	640 KB	Output is correct
8	Correct	2 ms	640 KB	Output is correct
9	Correct	2 ms	640 KB	Output is correct
10	Correct	3 ms	652 KB	Output is correct
11	Correct	3 ms	656 KB	Output is correct
12	Correct	2 ms	656 KB	Output is correct
13	Correct	3 ms	664 KB	Output is correct
14	Correct	3 ms	672 KB	Output is correct
15	Correct	2 ms	672 KB	Output is correct
16	Correct	3 ms	672 KB	Output is correct
17	Correct	3 ms	684 KB	Output is correct
18	Correct	3 ms	688 KB	Output is correct
19	Correct	3 ms	692 KB	Output is correct
20	Correct	3 ms	752 KB	Output is correct
21	Correct	3 ms	752 KB	Output is correct
22	Correct	7 ms	976 KB	Output is correct
23	Correct	7 ms	980 KB	Output is correct
24	Correct	6 ms	984 KB	Output is correct
25	Correct	7 ms	988 KB	Output is correct
26	Correct	4 ms	988 KB	Output is correct
27	Correct	3 ms	988 KB	Output is correct
28	Correct	3 ms	988 KB	Output is correct
29	Correct	3 ms	988 KB	Output is correct

Subtask #3
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	4 ms	492 KB	Output is correct
3	Correct	2 ms	532 KB	Output is correct
4	Correct	3 ms	532 KB	Output is correct
5	Correct	2 ms	556 KB	Output is correct
6	Correct	2 ms	636 KB	Output is correct
7	Correct	3 ms	640 KB	Output is correct
8	Correct	2 ms	640 KB	Output is correct
9	Correct	2 ms	640 KB	Output is correct
10	Correct	3 ms	652 KB	Output is correct
11	Correct	3 ms	656 KB	Output is correct
12	Correct	2 ms	656 KB	Output is correct
13	Correct	3 ms	664 KB	Output is correct
14	Correct	3 ms	672 KB	Output is correct
15	Correct	2 ms	672 KB	Output is correct
16	Correct	3 ms	672 KB	Output is correct
17	Correct	3 ms	684 KB	Output is correct
18	Correct	3 ms	688 KB	Output is correct
19	Correct	3 ms	692 KB	Output is correct
20	Correct	3 ms	752 KB	Output is correct
21	Correct	3 ms	752 KB	Output is correct
22	Correct	7 ms	976 KB	Output is correct
23	Correct	7 ms	980 KB	Output is correct
24	Correct	6 ms	984 KB	Output is correct
25	Correct	7 ms	988 KB	Output is correct
26	Correct	4 ms	988 KB	Output is correct
27	Correct	3 ms	988 KB	Output is correct
28	Correct	3 ms	988 KB	Output is correct
29	Correct	3 ms	988 KB	Output is correct
30	Correct	443 ms	22592 KB	Output is correct
31	Correct	389 ms	22592 KB	Output is correct
32	Correct	206 ms	22592 KB	Output is correct
33	Execution timed out	2089 ms	343316 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	343316 KB	Output is correct
2	Correct	5 ms	343316 KB	Output is correct
3	Correct	7 ms	343316 KB	Output is correct
4	Correct	5 ms	343316 KB	Output is correct
5	Incorrect	6 ms	343316 KB	3rd lines differ - on the 1st token, expected: '2096', found: '1490'
6	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	4 ms	492 KB	Output is correct
3	Correct	2 ms	532 KB	Output is correct
4	Correct	3 ms	532 KB	Output is correct
5	Correct	2 ms	556 KB	Output is correct
6	Correct	2 ms	636 KB	Output is correct
7	Correct	3 ms	640 KB	Output is correct
8	Correct	2 ms	640 KB	Output is correct
9	Correct	2 ms	640 KB	Output is correct
10	Correct	3 ms	652 KB	Output is correct
11	Correct	3 ms	656 KB	Output is correct
12	Correct	2 ms	656 KB	Output is correct
13	Correct	3 ms	664 KB	Output is correct
14	Correct	3 ms	672 KB	Output is correct
15	Correct	2 ms	672 KB	Output is correct
16	Correct	3 ms	672 KB	Output is correct
17	Correct	3 ms	684 KB	Output is correct
18	Correct	3 ms	688 KB	Output is correct
19	Correct	3 ms	692 KB	Output is correct
20	Correct	3 ms	752 KB	Output is correct
21	Correct	3 ms	752 KB	Output is correct
22	Correct	7 ms	976 KB	Output is correct
23	Correct	7 ms	980 KB	Output is correct
24	Correct	6 ms	984 KB	Output is correct
25	Correct	7 ms	988 KB	Output is correct
26	Correct	4 ms	988 KB	Output is correct
27	Correct	3 ms	988 KB	Output is correct
28	Correct	3 ms	988 KB	Output is correct
29	Correct	3 ms	988 KB	Output is correct
30	Correct	443 ms	22592 KB	Output is correct
31	Correct	389 ms	22592 KB	Output is correct
32	Correct	206 ms	22592 KB	Output is correct
33	Execution timed out	2089 ms	343316 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

답안 #67911

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 28.0

Subtask #4 0 / 20.0

Subtask #5 0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 28.0

Subtask #4
0 / 20.0

Subtask #5
0 / 30.0