Submission #73395

#	Time	Username	Problem	Language	Result	Execution time	Memory
73395		Sa1378	고대 책들 (IOI17_books)	C++17	50 / 100	336 ms	16316 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N ((int)1001*1000)

int n;
ll prt[N],ans;

ll minimum_walk(vector<int> p, int s)
{
	n=p.size();
	int mini=s,maxi=s-1;
	int mini2=s,maxi2=s-1;
	for(int i=0;i<n;i++)
	{
		int l=min(i,p[i]),r=max(i,p[i]);
		if(r<=s)
		{
			if(l!=r)mini=min(mini,l);
			prt[(r>0)?r-1:N-1]++;
			prt[(l>0)?l-1:N-1]--;
		}
		else if(l>=s)
		{
			if(l!=r)maxi=max(maxi,r-1);
			prt[l]++;
			prt[r]--;
		}
		else
		{
			maxi2=max(maxi2,r-1);
			mini2=min(mini2,l);
			prt[s]++;prt[r]--;
			prt[(s>0)?s-1:N-1]++;
			prt[(l>0)?l-1:N-1]--;
		}
	}
	for(int i=s;i<n;i++)
	{
		if(i>s)prt[i]+=prt[i-1];
		ans+=prt[i];
	}
	for(int i=s-1;i>=0;i--)
	{
		if(i!=s-1)prt[i]+=prt[i+1];
		ans+=prt[i];
	}
//	cout<<mini<<" "<<mini2<<" "<<maxi<<" "<<maxi2<<"\n";
	ll res=0;
	for(int i=s;i<=max(maxi2,maxi);i++)if(!prt[i])res+=2;
	for(int i=s-1;i>=mini;i--)if(!prt[i])res+=2;
	ll res2=0;
	for(int i=s;i<=maxi;i++)if(!prt[i])res2+=2;
	for(int i=s-1;i>=min(mini2,mini);i--)if(!prt[i])res2+=2;
//	cout<<ans<<"\n";
	ans+=min(res,res2);
	return ans;
}

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