oj.uz

Submission #316876

# Submission time Handle Problem Language Result Execution time Memory
316876 2020-10-28T11:34:35 Z spatarel Comparing Plants (IOI20_plants) C++17
14 / 100
 928 ms 203896 KB 
#include "plants.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 gt[MAX_N][MAX_N];

void init(int k, std::vector<int> r) {
  int 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++) {
    //print(r);
    MoxRange moxRange = getMoxRange(k, r);
    //printf("%d > [%d..%d]\n", moxRange.mox, moxRange.l, moxRange.r);
    
    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 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");
  }//*/
  return;
}

int compare_plants(int x, int y) {
	return gt[x][y];
}

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 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Incorrect 0 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.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 256 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 24 ms 8320 KB Output is correct
7 Correct 901 ms 101192 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 24 ms 8320 KB Output is correct
10 Correct 907 ms 101104 KB Output is correct
11 Correct 546 ms 101112 KB Output is correct
12 Correct 562 ms 101240 KB Output is correct
13 Correct 928 ms 101112 KB Output is correct

Subtask #3
0 / 13.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 256 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 24 ms 8320 KB Output is correct
7 Correct 901 ms 101192 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 24 ms 8320 KB Output is correct
10 Correct 907 ms 101104 KB Output is correct
11 Correct 546 ms 101112 KB Output is correct
12 Correct 562 ms 101240 KB Output is correct
13 Correct 928 ms 101112 KB Output is correct
14 Runtime error 285 ms 203896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 118 ms 26872 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.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 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.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 Incorrect 0 ms 256 KB Output isn't correct
4 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 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Incorrect 0 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -