Submission #1076034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076034		edogawa_something	Ancient Books (IOI17_books)	C++17	0 / 100	1 ms	2396 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pb push_back
ll n,pre[2000000],suf[2000000];
bool vis[2000000];
long long minimum_walk(vector<int> p, int s) {
  n=p.size();
  ll res=0;
  bool chk=1;
  for(int i=0;i<n;i++) {
    if(p[i]!=i)
      chk=0;
  }
  if(chk)
    return 0;
  pre[0]=2*(p[0]>0);
  res+=pre[0];
  for(int i=1;i<n;i++) {
    if(p[i]>=i)
      pre[i]+=2;
    vis[p[i]]=1;
    if(vis[i])
      pre[i]-=2;
    pre[i]+=pre[i-1];
    res+=pre[i];
  }
  res-=pre[n-1];
  memset(vis,0,sizeof vis);
  suf[n-1]=2*(p[n-1]<n-1);
  for(int i=n-2;i>=0;i--) {
    if(p[i]<=i)
      suf[i]+=2;
    vis[p[i]]=1;
    if(vis[i])
      suf[i]-=2;
    suf[i]+=suf[i+1];
  }
  ll l=0,r=n-1;
  for(int i=n-1;i>=0;i--) {
    if(suf[i]>0) {
      r=i;
      break;
    }
  }
  for(int i=0;i<n;i++) {
    if(pre[i]>0) {
      l=i;
      break;
    }
  }
  if(s<l)
    res+=2*(l-s);
  else if(s>r)
    res+=2*(s-r);
  else {
    memset(vis,0,sizeof vis);
    for(int i=s;i<n;i++) {
      if(p[i]==i)
        res+=2,vis[i]=1;
      else
        break;
    }
    for(int i=s-1;i>=0;i--) {
      if(p[i]==i)
        res+=2,vis[i]=1;
      else
        break;
    }
  }
    for(int i=l;i<r;i++) {
      if(!vis[i]&&pre[i]==0)
        res+=2;
    }
  return res;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30