oj.uz

Submission #328322

# Submission time Handle Problem Language Result Execution time Memory
328322 2020-11-16T06:21:15 Z arnold518 Ancient Books (IOI17_books) C++14
0 / 100
 1 ms 364 KB 
#include "books.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;

int N;
int A[MAXN+10], B[MAXN+10], S;
ll ans;

ll minimum_walk(vector<int> _P, int _S)
{
	N=_P.size(); S=_S+1;
	for(int i=1; i<=N; i++) A[i]=_P[i-1]+1;
	for(int i=1; i<=N; i++) B[A[i]]=i;

	for(int i=1; i<=N; i++) ans+=abs(i-A[i]);

	vector<pii> V;
	for(int i=1; i<=N; i++)
	{
		int l=min(i, A[i]), r=max(i, A[i]);
		V.push_back({l, r});
	}

	sort(V.begin(), V.end());
	int p=0, q=0;
	vector<pii> VV;

	for(auto it : V)
	{
		if(q<it.first)
		{
			if(p) VV.push_back({p, q});
			p=it.first; q=it.second;
		}
		q=it.second;
	}
	if(p) VV.push_back({p, q});

	ans+=(VV.size()-1)*2;
	for(int i=0; i<VV.size() && VV[i].first==VV[i].second && VV[i].second<S; i++) ans-=2;
	for(int i=VV.size()-1; i>=0 && VV[i].first==VV[i].second && VV[i].first>S; i--) ans-=2;
	return ans;
}

Compilation message

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i=0; i<VV.size() && VV[i].first==VV[i].second && VV[i].second<S; i++) ans-=2;
      |               ~^~~~~~~~~~

Subtask #1
0 / 12.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

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