#include "books.h"
#define f first
#define s second
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> tab;
void solve(int a, int b, int &na, int &nb){
//cout<<a<<" "<<b<<" "<<na<<" "<<nb<<'\n';
int ta = na;
int tb = nb;
for(int i = na; i <= a; i++){
if(tab[i].f!=-1){
ta = min(ta, tab[i].f);
tb = max(tb, tab[i].s);
//cout<<i<<" "<<tab[i].f<<" "<<tab[i].s<<'\n';
}
}
for(int i = b; i <= nb; i++){
if(tab[i].f!=-1){
ta = min(ta, tab[i].f);
tb = max(tb, tab[i].s);
//cout<<i<<" "<<tab[i].f<<" "<<tab[i].s<<'\n';
}
}
if(ta!=na||nb!=tb) solve(na-1, nb+1, ta, tb);
na = ta;
nb = tb;
}
long long minimum_walk(std::vector<int> p, int s) {
int n = p.size();
vector<int> odw(n);
long long wyn = 0;
vector<pair<int, int>> inp;
vector<pair<int, int>> inp2;
tab.resize(n, {-1, -1});
int globMax=-1e9, globMin=1e9;
for(int i = 0; i < n; i++){
int pt = i;
if(!odw[pt]){
if(p[pt]!=pt){
int mini = 1e9;
int maxi = -1e9;
while(!odw[pt]){
mini = min(mini, pt);
maxi = max(maxi, pt);
odw[pt] = true;
wyn+=abs(p[pt]-pt);
pt = p[pt];
}
globMax = max(globMax, maxi);
globMin = min(globMin, mini);
tab[i] = {mini, maxi};
inp2.push_back({mini, -i});
inp2.push_back({maxi, i});
inp.push_back({mini, maxi});
}else{
tab[i] = {-1, -1};
odw[pt] = true;
}
}
}
inp.push_back({s, s});
sort(inp.begin(), inp.end());
int dal = -1;
int cA=-1, cB=-1;
bool bylo = false;
for(int i = 0; i < inp.size(); i++){
while(dal>inp[i].f){
dal = max(dal, inp[i].s);
i++;
if(i>=inp.size()) break;
}
if(dal>=s){
cB = dal;
bylo = true;
}
if(i<inp.size()){
if(i!=0) wyn+=2*(inp[i].f-dal);
dal = inp[i].s;
}
if(!bylo) cA=inp[i].f;
}
int pocz=s, kon=s;
//cout<<cA<<" "<<cB<<'\n';
while(true){
//cout<<pocz<<" "<<kon<<'\n';
solve(pocz, kon, pocz, kon);
//cout<<pocz<<" "<<kon<<'\n';
if(pocz>cA||kon<cB){
wyn+=2;
pocz--;
kon++;
}else break;
}
return wyn;
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i = 0; i < inp.size(); i++){
| ~~^~~~~~~~~~~~
books.cpp:76:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | if(i>=inp.size()) break;
| ~^~~~~~~~~~~~
books.cpp:82:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | if(i<inp.size()){
| ~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
296 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
292 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
296 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
296 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
292 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
296 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Incorrect |
1 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '2082', found: '3092' |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
296 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
292 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
296 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Incorrect |
1 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '2082', found: '3092' |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3512' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
296 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
292 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
296 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Incorrect |
1 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '2082', found: '3092' |
| 23 |
Halted |
0 ms |
0 KB |
- |
