Submission #121972

#TimeUsernameProblemLanguageResultExecution timeMemory
121972nvmdavaAncient Books (IOI17_books)C++17
50 / 100
228 ms20712 KiB
#include "books.h" #include <bits/stdc++.h> using namespace std; bool in[1000005]; vector<pair<int, int> > cyc, tmp; int mn, mx; long long res; void dfs(int i, vector<int>& p){ if(in[i]) return; in[i] = 1; mx = max(mx, i); mn = min(mn, i); dfs(p[i], p); } long long minimum_walk(std::vector<int> p, int s) { for(int i = 0; i < p.size(); i++){ res += abs(p[i] - i); if(in[i]) continue; mn = i; mx = i; dfs(i, p); if(mn != mx)tmp.push_back({mn , mx}); } if(tmp.empty()) return 0; sort(tmp.begin(), tmp.end()); mx = -1; for(auto& x : tmp){ if(mx < x.first){ if(!cyc.empty()){ res += 2 * (x.first - mx); } cyc.push_back(x); } mx = max(mx, x.second); } if(s < cyc[0].first) res += 2 * (cyc[0].first - s); if(s > cyc.back().second) res += 2 * (s - cyc.back().second); return res; }

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:18:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < p.size(); i++){
                 ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...