oj.uz

Submission #1076026

# Submission time Handle Problem Language Result Execution time Memory
1076026 2024-08-26T10:36:30 Z edogawa_something Ancient Books (IOI17_books) C++17
0 / 100
 2 ms 2396 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 2 ms 2392 KB Output is correct
5 Incorrect 1 ms 2396 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 2 ms 2392 KB Output is correct
5 Incorrect 1 ms 2396 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 2 ms 2392 KB Output is correct
5 Incorrect 1 ms 2396 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2392 KB 3rd lines differ - on the 1st token, expected: '3304', found: '4740'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 2 ms 2392 KB Output is correct
5 Incorrect 1 ms 2396 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -