제출 #1104940

#제출 시각아이디문제언어결과실행 시간메모리
1104940alexander707070고대 책들 (IOI17_books)C++14
50 / 100
110 ms28760 KiB
#include<bits/stdc++.h> #define MAXN 1000007 using namespace std; int n,s,p[MAXN],fr,last,mins,maxs,pref[MAXN],curr; bool li[MAXN]; long long ans; int k,cycle[MAXN]; pair<int,int> where[MAXN]; void dfs(int x){ li[x]=true; cycle[x]=k; ans+=abs(x-p[x]); mins=min(mins,x); maxs=max(maxs,x); if(!li[p[x]])dfs(p[x]); } long long minimum_walk(vector<int> P, int S){ n=int(P.size()); s=S+1; for(int i=1;i<=n;i++){ p[i]=P[i-1]+1; li[i]=false; pref[i]=0; } last=0; fr=n+1; k=0; ans=0; for(int i=1;i<=n;i++){ if(!li[i]){ if(p[i]!=i)last=i; dfs(i); } } for(int i=1;i<=n;i++)li[i]=false; for(int i=n;i>=1;i--){ if(!li[i]){ k++; if(p[i]!=i)fr=i; mins=n; maxs=1; dfs(i); where[k]={mins,maxs}; pref[mins]++; pref[maxs]--; } } ans/=2; for(int i=1;i<=n-1;i++){ curr+=pref[i]; if(i<s)continue; if(curr==0 and last>i)ans+=2; } curr=0; for(int i=n;i>=2;i--){ curr+=pref[i]; if(i>s)continue; if(curr==0 and fr<i)ans+=2; } /// more steps inside initial cycle vector<int> l,r; int pt=s,from=s,to=s,ll=s,rr=s; while(true){ if(ll>=from){ from=min(from,where[cycle[ll]].first); to=max(to,where[cycle[ll]].second); ll--; } if(rr<=to){ from=min(from,where[cycle[rr]].first); to=max(to,where[cycle[rr]].second); rr++; } if(ll<from and rr>to)break; } pt=to; while(pt<=n){ int t=0; pt=where[cycle[pt]].second+1; t++; while(pt<=n and where[cycle[pt]].first>=s){ if(where[cycle[pt]].second==pt){ pt++; t++; }else{ pt++; } } if(pt<=n)r.push_back(t); } pt=from; while(pt>1){ int t=0; pt=where[cycle[pt]].first-1; t++; while(pt>=1 and where[cycle[pt]].second<=s){ if(where[cycle[pt]].first==pt){ pt--; t++; }else{ pt--; } } if(pt>=1)l.push_back(t); } for(int i=0;i<l.size();i++){ ans+=2*min(l[i],r[i]); } return ans; } /*int main(){ vector<int> perm; for(int i=0;i<20;i++){ perm.push_back(i); } while(true){ random_shuffle(perm.begin(),perm.end()); for(int i=0;i<20;i++){ cout<<perm[i]<<" "; } cout<<"\n"; int z=rand()%20; cout<<z<<"\n"; minimum_walk(perm,z); } return 0; }*/

컴파일 시 표준 에러 (stderr) 메시지

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:130:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |  for(int i=0;i<l.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...