oj.uz

Submission #316875

# Submission time Handle Problem Language Result Execution time Memory
316875 2020-10-28T11:33:28 Z spatarel Comparing Plants (IOI20_plants) C++17
11 / 100
 88 ms 6136 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 = 300;

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 Correct 0 ms 256 KB Output is correct
6 Correct 64 ms 3192 KB Output is correct
7 Runtime error 63 ms 6136 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 1 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 256 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Runtime error 3 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 256 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Runtime error 3 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 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 256 KB Output is correct
3 Runtime error 53 ms 5880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 49 ms 1580 KB Output is correct
8 Correct 85 ms 1656 KB Output is correct
9 Correct 60 ms 1656 KB Output is correct
10 Correct 83 ms 1704 KB Output is correct
11 Correct 50 ms 1656 KB Output is correct
12 Correct 53 ms 1656 KB Output is correct
13 Correct 88 ms 1700 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 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 256 KB Output is correct
5 Runtime error 2 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 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 Correct 0 ms 256 KB Output is correct
6 Correct 64 ms 3192 KB Output is correct
7 Runtime error 63 ms 6136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -