oj.uz

Submission #443962

# Submission time Handle Problem Language Result Execution time Memory
443962 2021-07-12T16:12:43 Z peijar Comparing Plants (IOI20_plants) C++17
19 / 100
 4000 ms 11848 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

/*
 * Si h[i] < h[i+1], alors r[i+1] <= r[i]
 * Si h[i] > h[i+1] alors r[i+1] >= r[i]
 * Donc si on a r[i] != r[i+1] on peut comparer r[i] et r[i+1] !
 * r[i+1] > r[i] => h[i+1] < h[i]
 * r[i+1] < r[i] => h[i+1] > h[i]
 */

const int MAXN = 2e5;

int k;
int nbPlusGrands[MAXN], cntEq[MAXN][2];
vector<int> adj[MAXN];
int ordre[MAXN];
int nbDevant[MAXN];
bool reach[301][301];
int nbPlantes;

int disCircle(int x, int y) {
  if (x < y)
    return y - x;
  return nbPlantes - x + y;
}

void init(int _k, vector<int> r) {
  k = _k;
  nbPlantes = r.size();
  for (int iPlante = 0; iPlante < nbPlantes; ++iPlante) {
    nbPlusGrands[iPlante] = r[iPlante];
  }

  if (k == 2) {
    for (int i = nbPlantes - 1; i >= 0; --i) {
      if (i == nbPlantes - 1) {
        int x = 1;
        while (x < nbPlantes and nbPlusGrands[x - 1] == nbPlusGrands[i])
          x++;
        cntEq[i][nbPlusGrands[i]] = x;
      } else {
        cntEq[i][nbPlusGrands[i]] = 1 + cntEq[i + 1][nbPlusGrands[i]];
      }
    }
  } else if (2 * k > nbPlantes) {
    for (int i = 0; i < nbPlantes; ++i)
      nbDevant[i] = k - 1, ordre[i] = -1;
    for (int iOrdre = 0; iOrdre < nbPlantes; ++iOrdre) {
      vector<int> possibles;
      for (int iPlante = 0; iPlante < nbPlantes; ++iPlante)
        if (ordre[iPlante] == -1 and nbDevant[iPlante] == nbPlusGrands[iPlante])
          possibles.push_back(iPlante);
      while (possibles.size() > 1) {
        int x = possibles.back();
        possibles.pop_back();
        int y = possibles.back();
        possibles.pop_back();
        if (disCircle(x, y) < k)
          possibles.push_back(x);
        else
          possibles.push_back(y);
      }
      int x = possibles.back();
      ordre[x] = iOrdre;
      for (int iPlante = 0; iPlante < nbPlantes; ++iPlante)
        if (disCircle(iPlante, x) < k and ordre[iPlante] == -1)
          nbDevant[iPlante]--;
    }
  } else {
    vector<bool> seen(nbPlantes);
    for (int iPlante = 0; iPlante < nbPlantes; ++iPlante)
      nbDevant[iPlante] = k - 1;
    int nbRestant = nbPlantes;
    while (nbRestant > 0) {
      vector<int> pot;
      for (int iPlante = 0; iPlante < nbPlantes; ++iPlante)
        if (!seen[iPlante] and nbDevant[iPlante] == nbPlusGrands[iPlante])
          pot.push_back(iPlante);
      vector<int> possibles;
      int nbPots = pot.size();
      for (int iPot = 0; iPot < nbPots; ++iPot) {
        int potAvant = iPot ? iPot - 1 : nbPots - 1;
        if (potAvant != iPot and disCircle(pot[potAvant], pot[iPot]) >= k)
          possibles.push_back(pot[iPot]);
      }

      for (int iPlante : possibles) {
        for (int j = 0; j < nbPlantes; ++j)
          if (disCircle(j, iPlante) < k and !seen[iPlante]) {
            nbDevant[j]--;
            adj[iPlante].push_back(j);
          }
        seen[iPlante] = false;
        nbRestant--;
      }
    }

    for (int i = 0; i < nbPlantes; ++i)
      reach[i][i] = 1;
    for (int i = 0; i < nbPlantes; ++i)
      for (int j : adj[i])
        reach[i][j] = 1;
    for (int inter = 0; inter < nbPlantes; ++inter)
      for (int i = 0; i < nbPlantes; ++i)
        if (reach[i][inter])
          for (int j = 0; j < nbPlantes; ++j)
            if (reach[inter][j])
              reach[i][j] = 1;
  }
}

int compare_plants(int x, int y) {
  if (k == 2) {
    bool allSame1[2] = {true, true};
    bool allSame2[2] = {true, true};
    int dis1 = disCircle(x, y);
    int dis2 = disCircle(y, x);
    for (int b = 0; b < 2; ++b) {
      allSame1[b] = cntEq[x][b] >= dis1;
      allSame2[b] = cntEq[y][b] >= dis2;
    }
    if (allSame1[0] or allSame2[1])
      return 1;
    else if (allSame1[1] or allSame2[0])
      return -1;
    return 0;
  } else if (2 * k > nbPlantes) {
    return (ordre[x] < ordre[y] ? -1 : 1);
  } else {
    if (reach[x][y] and reach[y][x])
      return 0;
    if (reach[x][y])
      return -1;
    return 1;
  }
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 5012 KB Output is correct
6 Correct 76 ms 8376 KB Output is correct
7 Correct 69 ms 8776 KB Output is correct
8 Correct 94 ms 11848 KB Output is correct
9 Correct 94 ms 11812 KB Output is correct
10 Correct 93 ms 11812 KB Output is correct
11 Correct 96 ms 11832 KB Output is correct
12 Correct 90 ms 11848 KB Output is correct
13 Correct 92 ms 11796 KB Output is correct
14 Correct 90 ms 11844 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 3 ms 5004 KB Output is correct
6 Correct 11 ms 5108 KB Output is correct
7 Correct 244 ms 8484 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 11 ms 5060 KB Output is correct
10 Correct 237 ms 8544 KB Output is correct
11 Correct 218 ms 8388 KB Output is correct
12 Correct 209 ms 8716 KB Output is correct
13 Correct 270 ms 8484 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 3 ms 5004 KB Output is correct
6 Correct 11 ms 5108 KB Output is correct
7 Correct 244 ms 8484 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 11 ms 5060 KB Output is correct
10 Correct 237 ms 8544 KB Output is correct
11 Correct 218 ms 8388 KB Output is correct
12 Correct 209 ms 8716 KB Output is correct
13 Correct 270 ms 8484 KB Output is correct
14 Correct 3191 ms 8780 KB Output is correct
15 Execution timed out 4078 ms 11812 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 5012 KB Output is correct
6 Correct 76 ms 8376 KB Output is correct
7 Correct 69 ms 8776 KB Output is correct
8 Correct 94 ms 11848 KB Output is correct
9 Correct 94 ms 11812 KB Output is correct
10 Correct 93 ms 11812 KB Output is correct
11 Correct 96 ms 11832 KB Output is correct
12 Correct 90 ms 11848 KB Output is correct
13 Correct 92 ms 11796 KB Output is correct
14 Correct 90 ms 11844 KB Output is correct
15 Correct 3 ms 4940 KB Output is correct
16 Correct 3 ms 4940 KB Output is correct
17 Correct 3 ms 5068 KB Output is correct
18 Correct 3 ms 5008 KB Output is correct
19 Correct 3 ms 5004 KB Output is correct
20 Correct 11 ms 5108 KB Output is correct
21 Correct 244 ms 8484 KB Output is correct
22 Correct 5 ms 5068 KB Output is correct
23 Correct 11 ms 5060 KB Output is correct
24 Correct 237 ms 8544 KB Output is correct
25 Correct 218 ms 8388 KB Output is correct
26 Correct 209 ms 8716 KB Output is correct
27 Correct 270 ms 8484 KB Output is correct
28 Correct 3191 ms 8780 KB Output is correct
29 Execution timed out 4078 ms 11812 KB Time limit exceeded
30 Halted 0 ms 0 KB -