Submission #1226637

#TimeUsernameProblemLanguageResultExecution timeMemory
1226637MalixAncient Books (IOI17_books)C++20
50 / 100
198 ms55456 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> q; if(c[s].F!=-1)q.push(s); ll cnt=0; while(l!=pos||r!=n-1){ while(!q.empty()){ int x=q.front(); q.pop(); ans+=cnt; cnt=0; REP(i,c[x].F,l)if(c[i].F!=-1)q.push(i); REP(i,r+1,c[x].S)if(c[i].F!=-1)q.push(i); l=min(l,c[x].F); r=max(r,c[x].S); } if(l!=pos||r!=n-1){ cnt+=2; if(l!=pos){ l--; if(c[l].F!=-1)q.push(l); } if(r!=n-1){ r++; if(c[r].F!=-1)q.push(r); } } } return ans+cnt*2LL; }
#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...