#include <bits/stdc++.h>
using namespace std;
const int c=1000002;
bool v[c];
long long sum;
int n, t[c], kezd, veg, kis, nagy, bh=c, jh, mini[c], maxi[c], x[3], y[3];
vector<int> akt;
void dfs(int a) {
if (v[a]) return;
v[a]=true, akt.push_back(a);
kis=min(kis, a), nagy=max(nagy, a);
dfs(t[a]);
}
void le() {
int pos=mini[kezd], d=kezd, db=0, v=maxi[kezd];
//cout << "kezdes " << bh << " " << pos << " " << v << " " << veg << "\n";
while(bh<pos && v<=veg) {
while(d>pos) {
d--;
pos=min(pos, mini[d]);
v=max(v, maxi[d]);
}
if (bh<pos && v<=veg) {
db++;
pos--, pos=mini[pos], v=max(v, maxi[pos]);
}
}
x[0]=db;
if (v>veg) x[1]=pos, x[2]=v;
else x[1]=-1;
}
void fel() {
int pos=maxi[veg], d=veg, db=0, k=mini[kezd];
while(kezd<=k && pos<jh) {
while(d<pos) {
d++;
pos=max(pos, maxi[d]);
k=min(k, mini[d]);
}
if (k<=kezd && pos<jh) {
db++;
pos++, pos=maxi[pos], k=min(k, mini[pos]);
}
}
y[0]=db;
}
long long minimum_walk(vector<int> p, int s) {
n=p.size(), kezd=s, veg=s, kis=s, nagy=s, bh, jh;
for (int i=0; i<n; i++) {
t[i]=p[i], sum+=abs(p[i]-i);
}
//cout << "sima " << sum << "\n";
for (int i=0; i<n; i++) {
if (t[i]!=i) {
if (bh==c) bh=i;
jh=i;
}
kis=n, nagy=0;
dfs(i);
for (int i=0; i<akt.size(); i++) mini[akt[i]]=kis, maxi[akt[i]]=nagy;
akt.clear();
}
/*for (int i=0; i<n; i++) {
cout << mini[i] << " " << maxi[i] << "\n";
}*/
while(bh<kezd || veg<jh) {
int p=mini[kezd], q=maxi[veg];
while(p<kezd || veg<q) {
p=min(x[1], mini[kezd]), q=max(q, maxi[veg]);
if (kezd>p) kezd--;
if (veg<q) veg++;
}
le(), fel();
cout << "ert " << x[0] << " " << y[0] << " " << x[1] << " " << x[2] << "\n";
if (x[1]==-1) {
sum+=2*(x[0]+y[0]);
break;
}
sum+=2*min(x[0], y[0]);
while(x[1]<kezd || veg<x[2]) {
x[1]=min(x[1], mini[kezd]), x[2]=max(x[2], maxi[veg]);
if (kezd>x[1]) kezd--;
if (veg<x[2]) veg++;
}
}
return sum;
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:49:51: warning: right operand of comma operator has no effect [-Wunused-value]
49 | n=p.size(), kezd=s, veg=s, kis=s, nagy=s, bh, jh;
| ^~
books.cpp:49:53: warning: right operand of comma operator has no effect [-Wunused-value]
49 | n=p.size(), kezd=s, veg=s, kis=s, nagy=s, bh, jh;
| ^
books.cpp:61:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (int i=0; i<akt.size(); i++) mini[akt[i]]=kis, maxi[akt[i]]=nagy;
| ~^~~~~~~~~~~
| # |
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 |
384 KB |
secret mismatch |
| 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 |
384 KB |
secret mismatch |
| 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 |
- |
