#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> cycle;
vector<int> p;
ll n;
ll minc = 1e9;
ll maxc = -1e9;
struct UFDS{
int n;
vector<int> parent;
UFDS(int _n){
n = _n;
parent.resize(n);
for (int i = 0; i<n; i++){
parent[i]=i;
}
}
int root(int i){
if (parent[i]==i){return i;}
return parent[i]=root(parent[i]);
}
void connect(int a, int b){
int ra = root(a);
int rb = root(b);
if (ra==rb){return;}
parent[ra]=rb;
}
bool connected(int a, int b){
return root(a) == root(b);
}
};
ll findcycle(ll i, ll ptr){
cycle[i] = ptr;
minc=min(minc,i);
maxc=max(maxc,i);
if (cycle[p[i]]!=-1){
return abs(i-p[i]);
} else {
return abs(i-p[i]) + findcycle(p[i], ptr);
}
}
ll minimum_walk(std::vector<int> px, int s) {
p = px;
n = p.size();
cycle.resize(n,-1);
ll cycledist = 0;
ll ptr = 0;
vector<pair<int,int>> cycleranges;
vector<ll> cyclewidth(n+1);
ll minv = 1e9;
ll maxv = -1e9;
for (ll i = 0; i<n; i++){
if (cycle[i]!=-1){continue;}
minc=1e9;maxc=-1e9;
ll dist = findcycle(i,ptr);
//if (dist!=0){
minv=min(minv,minc);
maxv=max(maxv,maxc);
//}
cycleranges.push_back({minc,maxc});
cyclewidth[minc]++;
cyclewidth[maxc]--;
cycledist+=dist;
ptr++;
}
ll prev = 0;
bool iszero = true;
ll ctr = 0;
ll minabove=1e9;
ll maxbelow=-1e9;
bool isbetween = false;
for (ll i = 0; i<=n; i++){
ctr+=cyclewidth[i];
if (ctr==0&&i==s){
isbetween=true;
}
if (iszero&&ctr>0){
if (i<=s){
maxbelow=max(maxbelow,i);
}
if (i>=s){
minabove=min(minabove,i);
}
if (prev!=0){cycledist+=2*(i-prev);}
iszero = false;
} else if ((!iszero)&&ctr==0){
if (i-1<=s){
maxbelow=max(maxbelow,i-1);
}
if (i-1>=s){
minabove=min(minabove,i-1);
}
prev = i;
iszero = true;
}
}
//cout<<maxbelow<<' '<<minabove<<endl;
if (maxbelow==-1e9&&minabove==1e9){
return 0;
} else if (s<=minv||s>=maxv){
return cycledist+2*min(minv-s,maxv-s);
} else if (!isbetween){
UFDS u(cycleranges.size());
for (int i = 0; i<cycleranges.size()-1; i++){
for (int j = i+1; j<cycleranges.size(); j++){
int as = cycleranges[i].first;
int ae = cycleranges[i].second;
int bs = cycleranges[j].first;
int be = cycleranges[j].second;
if ((as<=bs&&bs<=ae&&bs<=ae&&ae<=be)||(bs<=as&&as<=be&&as<=be&&be<=ae)){
u.connect(i,j);
}
}
}
vector<pair<int,int>> ranges(cycleranges.size(),{1e9,-1e9});
for (int i = 0; i<cycleranges.size(); i++){
int r = u.root(i);
ranges[r].first=min(ranges[r].first,cycleranges[r].first);
ranges[r].second=max(ranges[r].second,cycleranges[r].second);
}
vector<pair<int,int>> intersectingranges;
for (auto p : ranges){
if (p.first==1e9){continue;}
if (p.first<=s&&s<=p.second){
intersectingranges.push_back(p);
}
}
sort(intersectingranges.begin(),intersectingranges.end());
for (auto p : intersectingranges){
cout<<p.first<<' '<<p.second<<endl;
}
ll dist = 0;
for (int i = 0; i<intersectingranges.size()-1; i++){
dist+=min(abs(intersectingranges[i+1].first-intersectingranges[i].first),
abs(intersectingranges[i].second-intersectingranges[i+1].second));
}
//cout<<dist<<endl;
cycledist+=2*dist;
}
return cycledist;
}
Compilation message
books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:118:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for (int i = 0; i<cycleranges.size()-1; i++){
| ~^~~~~~~~~~~~~~~~~~~~~
books.cpp:119:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for (int j = i+1; j<cycleranges.size(); j++){
| ~^~~~~~~~~~~~~~~~~~~
books.cpp:130:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for (int i = 0; i<cycleranges.size(); i++){
| ~^~~~~~~~~~~~~~~~~~~
books.cpp:147:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for (int i = 0; i<intersectingranges.size()-1; i++){
| ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
3rd lines differ - on the 1st token, expected: '6', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
3rd lines differ - on the 1st token, expected: '6', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
3rd lines differ - on the 1st token, expected: '6', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
3rd lines differ - on the 1st token, expected: '6', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
