#include "books.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define fst first
#define snd second
#define FOR(i, l, r) for(int i = l; i < r; i++)
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
const int NMAX = 1e6 + 10;
const int INF = 1e9;
vi cycles[NMAX];
int numCycles, N;
bitset<NMAX> vis;
vi point;
void flood(int n, int c){
//cout << "Flood " << n << " " << c << endl;
cycles[c].pb(n);
int k = point[n];
vis[n] = 1;
if(!vis[k]) flood(k, c);
}
//
ii bounds(int p, int c){
//cout << p << endl;
auto &cy = cycles[c];
if(cy[0] > p) return {-1, cy[0]};
if(cy.back() <= p) return {cy.back(), INF};
auto x = lower_bound(cycles[c].begin(), cycles[c].end(), p);
return {*x, *(++x)};
}
long long minimum_walk(std::vector<int> p, int s) {
vis.reset();
point = p;
N = p.size();
FOR(i, 0, N) if(!vis[i]) flood(i, numCycles++);
FOR(i, 0, numCycles) sort(cycles[i].begin(), cycles[i].end());
//cout << "Preprocessed" << endl;
//ii k = bounds(2, 1);
//cout << k.fst << " " << k.snd << endl;
//Find segments:
vii segs;
int rm = 0;
int lm = 0;
//cout << "numCycles: " << numCycles << endl;
FOR(i, 0, numCycles){
//cout << lm << " " << rm << endl;
if(cycles[i].size() == 1) continue;
if(rm <= cycles[i][0]) {
if(rm - lm > 1) segs.pb({lm, rm});
lm = cycles[i][0]; rm = cycles[i].back()+1;
}
rm = max(rm, cycles[i].back()+1);
}
if(rm - lm > 1) segs.pb({lm, rm});
//cout << segs.size() << endl;
int dist = 0;
if(segs.size() > 0)
dist = segs[0].fst*2;
//cout << dist << endl;
FOR(i, 0, N) dist += abs(i - p[i]);
//cout << dist << endl;
//cout << segs.size() - 1 << endl;
FOR(i, 0, (int)segs.size()) cout << segs[i].fst << " " << segs[i].snd << endl;
FOR(i, 0, (int)segs.size()-1){
dist += 2*(segs[i+1].fst - (segs[i].snd-1) );
}
//cout << "sfdf" << endl;
return dist;
}
/*
3 1
0 2 1
4 0
0 1 3 2
4 0
2 3 0 1
4 0
0 1 2 3
10 0
0 1 4 5 2 3 7 6 9 8
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
23928 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
23928 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
23928 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
24040 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
23928 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
