Submission #51055

#TimeUsernameProblemLanguageResultExecution timeMemory
51055FLDutchmanAncient Books (IOI17_books)C++14
0 / 100
22 ms24364 KiB
#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){ //cerr << "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){ //cerr << p << endl; auto &cy = cycles[c]; if(cy[0] > p) return {-1, cy[0]}; if(cy[cy.size()-1] <= p) return {cy[cy.size()-1], 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; FOR(i, 0, numCycles){ //cout << lm << " " << rm << endl; 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()); } if(rm - lm > 1) segs.pb({lm, rm}); //cout << segs.size() << endl; int dist = segs[0].fst*2; FOR(i, 0, N) dist += abs(i - p[i]); FOR(i, 0, segs.size()-1){ dist += 2*(segs[i+1].fst - segs[i].snd); } return dist; } /* 3 1 0 2 1 */

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:8:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = l; i < r; i++)
books.cpp:69:6:
  FOR(i, 0, segs.size()-1){
      ~~~~~~~~~~~~~~~~~~~               
books.cpp:69:2: note: in expansion of macro 'FOR'
  FOR(i, 0, segs.size()-1){
  ^~~
#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...