oj.uz

Submission #68306

# Submission time Handle Problem Language Result Execution time Memory
68306 2018-08-16T13:16:32 Z zscoder Ancient Books (IOI17_books) C++17
100 / 100
 280 ms 265840 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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