제출 #1226717

#제출 시각아이디문제언어결과실행 시간메모리
1226717MalixAncient Books (IOI17_books)C++20
50 / 100
198 ms55492 KiB
#include "books.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vii; typedef pair<int,int> pi; typedef vector<pi> pii; typedef tuple<int,int,int> ti; typedef vector<ll> li; typedef vector<li> lii; #define REP(i,a,b) for(int i=a;i<b;i++) #define F first #define S second #define PB push_back #define LSOne(s) ((s)&(-s)) #define all(x) (x).begin(),(x).end() ll INF=1000000000000000010; int inf=1e9+10; ll M=1e9+7; vi a,vis,arr; void dfs(int x){ arr.PB(x); vis[x]=1; if(vis[a[x]]==0)dfs(a[x]); } long long minimum_walk(std::vector<int> p, int s) { a=p; while(a.size()&&a[a.back()]==a.back())a.pop_back(); if(a.size()==0)return 0; int n=a.size(); vis.resize(n,0); int pos=0; while(pos<n&&a[pos]==pos)pos++; ll ans=0; if(s>=n){ ans=(s-n+1)*2LL; s=n-1; } if(s<pos){ ans=(pos-s)*2LL; s=pos; } vector<pi> c(n,{-1,-1}); REP(i,pos,n)if(!vis[i]&&i!=a[i]){ arr.clear(); dfs(i); sort(all(arr)); for(auto u:arr)ans+=(ll)abs(u-a[u]); for(auto u:arr)c[u]={arr[0],arr.back()}; } int l=s,r=s; queue<int> L,R; if(c[s].F!=-1)L.push(s); ll cl=0,cr=0; while(!L.empty()){ int x=L.front(); L.pop(); if(c[x].F<=l&&c[x].S>=r){ ans+=cl; cl=0;cr=0; } REP(i,c[x].F,l)if(c[i].F!=-1)L.push(i); REP(i,r+1,c[x].S+1)if(c[i].F!=-1)L.push(i); l=min(l,c[x].F); r=max(r,c[x].S); } while(l!=pos||r!=n-1){ if(l!=pos){ l--; if(c[l].F!=-1)L.push(l); cl+=2; } if(r!=n-1){ r++; if(c[r].F!=-1)R.push(r); cr+=2; } int lt=l,rt=r; l=n;r=-1; while(!L.empty()){ int x=L.front(); L.pop(); REP(i,c[x].F,min(l,lt))if(c[i].F!=-1)L.push(i); REP(i,max(r,rt)+1,c[x].S+1)if(c[i].F!=-1)L.push(i); l=min(l,c[x].F); r=max(r,c[x].S); } if(l<=lt&&r>=rt){ ans+=cl; cl=0;cr=0; } while(!R.empty()){ int x=R.front(); R.pop(); REP(i,c[x].F,min(l,lt))if(c[i].F!=-1)R.push(i); REP(i,max(r,rt)+1,c[x].S+1)if(c[i].F!=-1)R.push(i); l=min(l,c[x].F); r=max(r,c[x].S); } if(l<=lt&&r>=rt){ ans+=cr; cl=0;cr=0; } l=min(l,lt); r=max(r,rt); } return ans+cl+cr; }
#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...