oj.uz

Submission #316892

# Submission time Handle Problem Language Result Execution time Memory
316892 2020-10-28T13:31:39 Z spatarel Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 48072 KB 
#include "plants.h"
#include <limits.h>
#include <stdio.h>

struct MoxRange {
  int mox;
  int l;
  int r;
};

MoxRange getMoxRange(int k, std::vector<int> &r) {
  int n = r.size();
  int i = n - 1;
  int positives = 0;
  while (i >= 0 && r[i] != 0) {
    i--;
    positives++;
  }
  int maxPositives = -1;
  int maxZero = 0;
  for (int i = 0; i < n; i++) {
    if (r[i] == 0 && maxPositives < positives) {
      maxPositives = positives;
      maxZero = i;
    }
    if (r[i] != 0) {
      positives++;
    } else {
      positives = 0;
    }
    //printf("i=%d posi=%d\n", i, positives);
  }
  MoxRange answer;
  answer.mox = maxZero;
  answer.l = maxZero - maxPositives;
  answer.r = maxZero + k - 1;
  /*
  if (answer.r - answer.l + 1 > n) {
    answer.r = answer.l + n - 1;
  }
  answer.l = (answer.l + n) % n;
  answer.r = (answer.r + n) % n;//*/
  
  r[maxZero] = -1;
  i = maxZero;
  for (int i = 0; i < k - 1; i++) {
    maxZero = (maxZero - 1 + n) % n;
    r[maxZero]--;
  }
	return answer;
}

void print(std::vector<int> &r) {
  int n = r.size();
  for (int i = 0; i < n; i++) {
    printf("%d ", r[i]);
  }
  printf("\n");
}

const int MAX_N = 5000;

int n;
int gt[MAX_N][MAX_N];
int leftGt[MAX_N];
int rightGt[MAX_N];

void init(int k, std::vector<int> r) {
  n = r.size();
  /*
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      gt[i][j] = 0;
    }
  }//*/
  for (int i = 0; i < n; i++) {
    leftGt[i] = INT_MIN;
    rightGt[i] = INT_MAX;
  }
  for (int i = 0; i < n; i++) {
    //print(r);
    MoxRange moxRange = getMoxRange(k, r);
    //printf("%d > [%d..%d]\n", moxRange.mox, moxRange.l, moxRange.r);
    
    for (int i = moxRange.mox + 1; i <= moxRange.r; i++) {
      if (r[i % n] >= 0) {
        if (i < n /*&& leftGt[i] < moxRange.mox*/) {
          leftGt[i] = moxRange.mox;
        }
        if (i >= n /*&& leftGt[i - n] < moxRange.mox - n*/) {
          leftGt[i - n] = moxRange.mox - n;
        }
      }
    }
    for (int i = moxRange.mox - 1; i >= moxRange.l; i--) {
      if (r[(i + n) % n] >= 0) {
        if (0 <= i /*&& moxRange.mox < rightGt[i]*/) {
          rightGt[i] = moxRange.mox;
        }
        if (0 > i /*&& moxRange.mox + n < rightGt[i + n]*/) {
          rightGt[i + n] = moxRange.mox + n;
        }
      }
    }
    
    /*
    int x = moxRange.l;
    do {
      if (x != moxRange.mox && gt[x][moxRange.mox] == 0 && r[x] >= 0) {
        gt[moxRange.mox][x] = +1;
        gt[x][moxRange.mox] = -1;
      }
      x = (x + 1) % n;
    } while (x != (moxRange.r + 1) % n);//*/
  }
  for (int i = 0; i < n; i++) {
    if (rightGt[i] != INT_MAX) {
      gt[i][rightGt[i] % n] = -1;
      gt[rightGt[i] % n][i] = +1;
    }
    if (leftGt[i] != INT_MIN) {
      gt[i][(leftGt[i] + n) % n] = -1;
      gt[(leftGt[i] + n) % n][i] = +1;
    }
  }
  //*
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        for (int value : {-1, +1}) {
          if (gt[i][k] == value && gt[k][j] == value) {
            gt[i][j] = value;
          }
        }
      }
    }
  }//*/
  
  /*
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      printf("%d ", gt[i][j]);
    }
    printf("\n");
  }//*/
  
  /*
  for (int i = 0; i < n; i++) {
    printf("%d ", rightGt[i]);
  }
  printf("\n");
  for (int i = 0; i < n; i++) {
    printf("%d ", leftGt[i]);
  }
  printf("\n");//*/
  return;
}

int compare_plants(int x, int y) {
  //assert(x < y);
  
  /*
  int src[] = { x,  y};
  int dest[]= { y,  x};
  int ans[] = {-1, +1};
  for (int i : {0, 1}) {
    int pos = src[i];
    while (rightGt[pos] != INT_MAX && pos != dest[i]) {
      pos = rightGt[pos] % n;
    }
    if (pos == dest[i]) {
      return ans[i];
    }
    pos = y;
    while (leftGt[pos] != INT_MIN && pos != x) {
      pos = leftGt[pos] % n;
    }
    if (pos == x) {
      return +1;
    }
  }//*/
  return gt[x][y];
  return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 62 ms 3192 KB Output is correct
7 Runtime error 1411 ms 5880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 1187 ms 8412 KB Output is correct
7 Execution timed out 4072 ms 48072 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 1187 ms 8412 KB Output is correct
7 Execution timed out 4072 ms 48072 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Execution timed out 4051 ms 16632 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 4 ms 888 KB Output is correct
7 Correct 50 ms 2680 KB Output is correct
8 Correct 65 ms 2808 KB Output is correct
9 Correct 55 ms 2876 KB Output is correct
10 Correct 63 ms 2808 KB Output is correct
11 Correct 49 ms 2680 KB Output is correct
12 Correct 52 ms 2808 KB Output is correct
13 Correct 50 ms 2844 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1635 ms 8428 KB Output is correct
6 Execution timed out 4050 ms 7288 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 62 ms 3192 KB Output is correct
7 Runtime error 1411 ms 5880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -