Submission #169959

#TimeUsernameProblemLanguageResultExecution timeMemory
169959dennisstarAncient Books (IOI17_books)C++11
12 / 100
6 ms4344 KiB
#include "books.h" #include <bits/stdc++.h> #define fi first #define se second #define ryan bear using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef long double ld; typedef vector<int> vim; int n; vim P; int fr, re; ll ret; vector<pii> im, ar, fin; ll minimum_walk(vim p, int s) { n=p.size(); for (fr=0; fr<n&&p[fr]==fr; fr++) {} for (re=n-1; re>=0&&p[re]==re; re--) {} for (int i=0; i<n; i++) ret+=abs(p[i]-i); if (!ret) return 0; vim chk(1000010); int mx; for (int i=fr; i<=re; i++) { if (chk[i]) continue; mx=0; for (int j=i; !chk[j]; j=p[j]) { chk[j]=1; mx=max(mx, j); } im.push_back({i, mx}); } sort(im.begin(), im.end()); mx=0; for (pii pi:im) { if (pi.se<mx) continue; mx=pi.se; ar.push_back(pi); } for (int i=0; i<ar.size(); i++) { fin.push_back({ar[i].fi, i}); fin.push_back({ar[i].se, i}); } sort(fin.begin(), fin.end()); int l; ll an1=0, an2=0; for (l=0; l<fin.size(); l++) if (fin[l].fi>=s) break; int lst=s; fill(chk.begin(), chk.end(), 0); for (int i=l; i<fin.size(); i++) { if (chk[fin[i].se]) continue; chk[fin[i].se]=1; an1+=abs(fin[i].fi-lst); lst=fin[i].fi; } for (int i=l-1; i>=0; i--) { if (chk[fin[i].se]) continue; chk[fin[i].se]=1; an1+=abs(fin[i].fi-lst); lst=fin[i].fi; } an1+=abs(lst-s); lst=s; fill(chk.begin(), chk.end(), 0); for (int i=l-1; i>=0; i--) { if (chk[fin[i].se]) continue; chk[fin[i].se]=1; an2+=abs(fin[i].fi-lst); lst=fin[i].fi; } for (int i=l; i<fin.size(); i++) { if (chk[fin[i].se]) continue; chk[fin[i].se]=1; an2+=abs(fin[i].fi-lst); lst=fin[i].fi; } an2+=abs(lst-s); return min(an1, an2)+ret; }

Compilation message (stderr)

books.cpp: In function 'll minimum_walk(vim, int)':
books.cpp:46:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<ar.size(); i++) {
                ~^~~~~~~~~~
books.cpp:53:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (l=0; l<fin.size(); l++) if (fin[l].fi>=s) break;
            ~^~~~~~~~~~~
books.cpp:57:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=l; i<fin.size(); i++) {
                ~^~~~~~~~~~~
books.cpp:79:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=l; i<fin.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...