oj.uz

Submission #73394

# Submission time Handle Problem Language Result Execution time Memory
73394 2018-08-28T08:13:24 Z Sa1378 Ancient Books (IOI17_books) C++17
0 / 100
 3 ms 620 KB 
#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;
	int mini2=s,maxi2=s;
	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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 3 ms 520 KB Output is correct
6 Correct 2 ms 564 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Incorrect 2 ms 620 KB 3rd lines differ - on the 1st token, expected: '0', found: '2'
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 3 ms 520 KB Output is correct
6 Correct 2 ms 564 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Incorrect 2 ms 620 KB 3rd lines differ - on the 1st token, expected: '0', found: '2'
10 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 3 ms 520 KB Output is correct
6 Correct 2 ms 564 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Incorrect 2 ms 620 KB 3rd lines differ - on the 1st token, expected: '0', found: '2'
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 620 KB 3rd lines differ - on the 1st token, expected: '3304', found: '2744'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 3 ms 520 KB Output is correct
6 Correct 2 ms 564 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Incorrect 2 ms 620 KB 3rd lines differ - on the 1st token, expected: '0', found: '2'
10 Halted 0 ms 0 KB -