답안 #68306 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68306	2018-08-16T13:16:32 Z	zscoder	고대 책들 (IOI17_books)	C++17	100 / 100	280 ms	265840 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)];
}

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

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

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	360 KB	Output is correct
3	Correct	2 ms	472 KB	Output is correct
4	Correct	3 ms	712 KB	Output is correct
5	Correct	2 ms	712 KB	Output is correct
6	Correct	3 ms	740 KB	Output is correct
7	Correct	3 ms	740 KB	Output is correct
8	Correct	2 ms	756 KB	Output is correct
9	Correct	2 ms	756 KB	Output is correct
10	Correct	2 ms	756 KB	Output is correct
11	Correct	3 ms	756 KB	Output is correct
12	Correct	3 ms	772 KB	Output is correct
13	Correct	2 ms	772 KB	Output is correct
14	Correct	3 ms	796 KB	Output is correct
15	Correct	3 ms	796 KB	Output is correct
16	Correct	4 ms	796 KB	Output is correct
17	Correct	3 ms	796 KB	Output is correct
18	Correct	2 ms	796 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	360 KB	Output is correct
3	Correct	2 ms	472 KB	Output is correct
4	Correct	3 ms	712 KB	Output is correct
5	Correct	2 ms	712 KB	Output is correct
6	Correct	3 ms	740 KB	Output is correct
7	Correct	3 ms	740 KB	Output is correct
8	Correct	2 ms	756 KB	Output is correct
9	Correct	2 ms	756 KB	Output is correct
10	Correct	2 ms	756 KB	Output is correct
11	Correct	3 ms	756 KB	Output is correct
12	Correct	3 ms	772 KB	Output is correct
13	Correct	2 ms	772 KB	Output is correct
14	Correct	3 ms	796 KB	Output is correct
15	Correct	3 ms	796 KB	Output is correct
16	Correct	4 ms	796 KB	Output is correct
17	Correct	3 ms	796 KB	Output is correct
18	Correct	2 ms	796 KB	Output is correct
19	Correct	4 ms	804 KB	Output is correct
20	Correct	4 ms	808 KB	Output is correct
21	Correct	3 ms	808 KB	Output is correct
22	Correct	3 ms	816 KB	Output is correct
23	Correct	3 ms	820 KB	Output is correct
24	Correct	3 ms	824 KB	Output is correct
25	Correct	3 ms	828 KB	Output is correct
26	Correct	2 ms	832 KB	Output is correct
27	Correct	3 ms	836 KB	Output is correct
28	Correct	2 ms	844 KB	Output is correct
29	Correct	3 ms	848 KB	Output is correct

Subtask #3
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	360 KB	Output is correct
3	Correct	2 ms	472 KB	Output is correct
4	Correct	3 ms	712 KB	Output is correct
5	Correct	2 ms	712 KB	Output is correct
6	Correct	3 ms	740 KB	Output is correct
7	Correct	3 ms	740 KB	Output is correct
8	Correct	2 ms	756 KB	Output is correct
9	Correct	2 ms	756 KB	Output is correct
10	Correct	2 ms	756 KB	Output is correct
11	Correct	3 ms	756 KB	Output is correct
12	Correct	3 ms	772 KB	Output is correct
13	Correct	2 ms	772 KB	Output is correct
14	Correct	3 ms	796 KB	Output is correct
15	Correct	3 ms	796 KB	Output is correct
16	Correct	4 ms	796 KB	Output is correct
17	Correct	3 ms	796 KB	Output is correct
18	Correct	2 ms	796 KB	Output is correct
19	Correct	4 ms	804 KB	Output is correct
20	Correct	4 ms	808 KB	Output is correct
21	Correct	3 ms	808 KB	Output is correct
22	Correct	3 ms	816 KB	Output is correct
23	Correct	3 ms	820 KB	Output is correct
24	Correct	3 ms	824 KB	Output is correct
25	Correct	3 ms	828 KB	Output is correct
26	Correct	2 ms	832 KB	Output is correct
27	Correct	3 ms	836 KB	Output is correct
28	Correct	2 ms	844 KB	Output is correct
29	Correct	3 ms	848 KB	Output is correct
30	Correct	191 ms	23380 KB	Output is correct
31	Correct	244 ms	30196 KB	Output is correct
32	Correct	146 ms	32788 KB	Output is correct
33	Correct	165 ms	39532 KB	Output is correct
34	Correct	252 ms	46212 KB	Output is correct
35	Correct	169 ms	53020 KB	Output is correct
36	Correct	166 ms	59816 KB	Output is correct
37	Correct	195 ms	66564 KB	Output is correct
38	Correct	185 ms	73328 KB	Output is correct
39	Correct	254 ms	80124 KB	Output is correct
40	Correct	193 ms	87084 KB	Output is correct
41	Correct	177 ms	95644 KB	Output is correct
42	Correct	199 ms	101892 KB	Output is correct
43	Correct	161 ms	110744 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	110744 KB	Output is correct
2	Correct	3 ms	110744 KB	Output is correct
3	Correct	3 ms	110744 KB	Output is correct
4	Correct	3 ms	110744 KB	Output is correct
5	Correct	2 ms	110744 KB	Output is correct
6	Correct	3 ms	110744 KB	Output is correct
7	Correct	2 ms	110744 KB	Output is correct
8	Correct	3 ms	110744 KB	Output is correct
9	Correct	2 ms	110744 KB	Output is correct
10	Correct	4 ms	110744 KB	Output is correct
11	Correct	3 ms	110744 KB	Output is correct
12	Correct	3 ms	110744 KB	Output is correct
13	Correct	3 ms	110744 KB	Output is correct
14	Correct	2 ms	110744 KB	Output is correct
15	Correct	2 ms	110744 KB	Output is correct
16	Correct	3 ms	110744 KB	Output is correct
17	Correct	3 ms	110744 KB	Output is correct
18	Correct	3 ms	110744 KB	Output is correct
19	Correct	2 ms	110744 KB	Output is correct
20	Correct	3 ms	110744 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	360 KB	Output is correct
3	Correct	2 ms	472 KB	Output is correct
4	Correct	3 ms	712 KB	Output is correct
5	Correct	2 ms	712 KB	Output is correct
6	Correct	3 ms	740 KB	Output is correct
7	Correct	3 ms	740 KB	Output is correct
8	Correct	2 ms	756 KB	Output is correct
9	Correct	2 ms	756 KB	Output is correct
10	Correct	2 ms	756 KB	Output is correct
11	Correct	3 ms	756 KB	Output is correct
12	Correct	3 ms	772 KB	Output is correct
13	Correct	2 ms	772 KB	Output is correct
14	Correct	3 ms	796 KB	Output is correct
15	Correct	3 ms	796 KB	Output is correct
16	Correct	4 ms	796 KB	Output is correct
17	Correct	3 ms	796 KB	Output is correct
18	Correct	2 ms	796 KB	Output is correct
19	Correct	4 ms	804 KB	Output is correct
20	Correct	4 ms	808 KB	Output is correct
21	Correct	3 ms	808 KB	Output is correct
22	Correct	3 ms	816 KB	Output is correct
23	Correct	3 ms	820 KB	Output is correct
24	Correct	3 ms	824 KB	Output is correct
25	Correct	3 ms	828 KB	Output is correct
26	Correct	2 ms	832 KB	Output is correct
27	Correct	3 ms	836 KB	Output is correct
28	Correct	2 ms	844 KB	Output is correct
29	Correct	3 ms	848 KB	Output is correct
30	Correct	191 ms	23380 KB	Output is correct
31	Correct	244 ms	30196 KB	Output is correct
32	Correct	146 ms	32788 KB	Output is correct
33	Correct	165 ms	39532 KB	Output is correct
34	Correct	252 ms	46212 KB	Output is correct
35	Correct	169 ms	53020 KB	Output is correct
36	Correct	166 ms	59816 KB	Output is correct
37	Correct	195 ms	66564 KB	Output is correct
38	Correct	185 ms	73328 KB	Output is correct
39	Correct	254 ms	80124 KB	Output is correct
40	Correct	193 ms	87084 KB	Output is correct
41	Correct	177 ms	95644 KB	Output is correct
42	Correct	199 ms	101892 KB	Output is correct
43	Correct	161 ms	110744 KB	Output is correct
44	Correct	2 ms	110744 KB	Output is correct
45	Correct	3 ms	110744 KB	Output is correct
46	Correct	3 ms	110744 KB	Output is correct
47	Correct	3 ms	110744 KB	Output is correct
48	Correct	2 ms	110744 KB	Output is correct
49	Correct	3 ms	110744 KB	Output is correct
50	Correct	2 ms	110744 KB	Output is correct
51	Correct	3 ms	110744 KB	Output is correct
52	Correct	2 ms	110744 KB	Output is correct
53	Correct	4 ms	110744 KB	Output is correct
54	Correct	3 ms	110744 KB	Output is correct
55	Correct	3 ms	110744 KB	Output is correct
56	Correct	3 ms	110744 KB	Output is correct
57	Correct	2 ms	110744 KB	Output is correct
58	Correct	2 ms	110744 KB	Output is correct
59	Correct	3 ms	110744 KB	Output is correct
60	Correct	3 ms	110744 KB	Output is correct
61	Correct	3 ms	110744 KB	Output is correct
62	Correct	2 ms	110744 KB	Output is correct
63	Correct	3 ms	110744 KB	Output is correct
64	Correct	190 ms	117920 KB	Output is correct
65	Correct	180 ms	124580 KB	Output is correct
66	Correct	251 ms	131068 KB	Output is correct
67	Correct	169 ms	137132 KB	Output is correct
68	Correct	30 ms	137132 KB	Output is correct
69	Correct	20 ms	137132 KB	Output is correct
70	Correct	25 ms	137132 KB	Output is correct
71	Correct	22 ms	137132 KB	Output is correct
72	Correct	24 ms	137132 KB	Output is correct
73	Correct	36 ms	137132 KB	Output is correct
74	Correct	164 ms	144152 KB	Output is correct
75	Correct	182 ms	150888 KB	Output is correct
76	Correct	195 ms	161788 KB	Output is correct
77	Correct	170 ms	168352 KB	Output is correct
78	Correct	199 ms	172548 KB	Output is correct
79	Correct	169 ms	179388 KB	Output is correct
80	Correct	149 ms	184612 KB	Output is correct
81	Correct	236 ms	192760 KB	Output is correct
82	Correct	253 ms	199488 KB	Output is correct
83	Correct	216 ms	204900 KB	Output is correct
84	Correct	223 ms	211700 KB	Output is correct
85	Correct	219 ms	218436 KB	Output is correct
86	Correct	175 ms	225208 KB	Output is correct
87	Correct	280 ms	231876 KB	Output is correct
88	Correct	252 ms	238620 KB	Output is correct
89	Correct	175 ms	245348 KB	Output is correct
90	Correct	204 ms	252096 KB	Output is correct
91	Correct	179 ms	259028 KB	Output is correct
92	Correct	206 ms	265840 KB	Output is correct

답안 #68306

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 28.0 / 28.0

Subtask #4 20.0 / 20.0

Subtask #5 30.0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
10.0 / 10.0

Subtask #3
28.0 / 28.0

Subtask #4
20.0 / 20.0

Subtask #5
30.0 / 30.0