oj.uz

Submission #72799

# Submission time Handle Problem Language Result Execution time Memory
72799 2018-08-27T01:37:04 Z funcsr Ancient Books (IOI17_books) C++17
0 / 100
 44 ms 47696 KB 
#include "books.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cassert>
using namespace std;
#define rep(i,n)for (int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define _1 first
#define _2 second
#define INF 1145141919
typedef pair<int, int> P;

int N;
bool used[1000000];
vector<int> G[1000000];

long long minimum_walk(vector<int> A, int S) {
  N = A.size();
  long long cost = 0;
  int lmin = 0, rmin = 0;
  rep(i, N) if (!used[i]) {
    if (i == A[i]) continue;
    int x = i;
    int left = -INF, right = INF;
    while (!used[x]) {
      if (x <= S) left = max(left, S-x);
      else right = min(right, x-S);
      used[x] = true;
      cost += abs(A[x]-x);
      x = A[x];
    }
    if (left == -INF) rmin = max(rmin, right);
    else if (right == INF) lmin = max(lmin, left);
    else {
      G[left].pb(right);
    }
    //cout<<left<<"<->"<<right<<"\n";
  }
  assert(S==0);
  int m = rmin;
  /*
  int m = INF;
  for (int left=N-1; left>=lmin; left--) {
    m = min(m, left+rmin);
    for (int r : G[left]) rmin = max(rmin, r);
  }
  */
  return cost+2LL*m;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 21 ms 23800 KB Output is correct
3 Correct 21 ms 23984 KB Output is correct
4 Correct 25 ms 23984 KB Output is correct
5 Correct 22 ms 23984 KB Output is correct
6 Incorrect 25 ms 24108 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 21 ms 23800 KB Output is correct
3 Correct 21 ms 23984 KB Output is correct
4 Correct 25 ms 23984 KB Output is correct
5 Correct 22 ms 23984 KB Output is correct
6 Incorrect 25 ms 24108 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 21 ms 23800 KB Output is correct
3 Correct 21 ms 23984 KB Output is correct
4 Correct 25 ms 23984 KB Output is correct
5 Correct 22 ms 23984 KB Output is correct
6 Incorrect 25 ms 24108 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 47696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 21 ms 23800 KB Output is correct
3 Correct 21 ms 23984 KB Output is correct
4 Correct 25 ms 23984 KB Output is correct
5 Correct 22 ms 23984 KB Output is correct
6 Incorrect 25 ms 24108 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -