oj.uz

Submission #443963

# Submission time Handle Problem Language Result Execution time Memory
443963 2021-07-12T16:14:03 Z peijar Comparing Plants (IOI20_plants) C++17
19 / 100
 4000 ms 11332 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 or disCircle(pot[potAvant], pot[iPot]) >= k)
          possibles.push_back(pot[iPot]);
      }
      assert(!possibles.empty());

      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 3 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 4940 KB Output is correct
6 Correct 63 ms 7748 KB Output is correct
7 Correct 68 ms 8200 KB Output is correct
8 Correct 97 ms 11208 KB Output is correct
9 Correct 94 ms 11212 KB Output is correct
10 Correct 95 ms 11204 KB Output is correct
11 Correct 92 ms 11188 KB Output is correct
12 Correct 89 ms 11208 KB Output is correct
13 Correct 87 ms 11316 KB Output is correct
14 Correct 89 ms 11192 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 4 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 11 ms 5068 KB Output is correct
7 Correct 232 ms 7876 KB Output is correct
8 Correct 5 ms 5004 KB Output is correct
9 Correct 11 ms 5068 KB Output is correct
10 Correct 218 ms 7896 KB Output is correct
11 Correct 167 ms 7776 KB Output is correct
12 Correct 205 ms 8004 KB Output is correct
13 Correct 247 ms 7848 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 4 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 11 ms 5068 KB Output is correct
7 Correct 232 ms 7876 KB Output is correct
8 Correct 5 ms 5004 KB Output is correct
9 Correct 11 ms 5068 KB Output is correct
10 Correct 218 ms 7896 KB Output is correct
11 Correct 167 ms 7776 KB Output is correct
12 Correct 205 ms 8004 KB Output is correct
13 Correct 247 ms 7848 KB Output is correct
14 Correct 3063 ms 8152 KB Output is correct
15 Execution timed out 4019 ms 11332 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Runtime error 8 ms 9932 KB Execution killed with signal 6
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 Runtime error 9 ms 9932 KB Execution killed with signal 6
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 Runtime error 9 ms 9932 KB Execution killed with signal 6
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 3 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 4940 KB Output is correct
6 Correct 63 ms 7748 KB Output is correct
7 Correct 68 ms 8200 KB Output is correct
8 Correct 97 ms 11208 KB Output is correct
9 Correct 94 ms 11212 KB Output is correct
10 Correct 95 ms 11204 KB Output is correct
11 Correct 92 ms 11188 KB Output is correct
12 Correct 89 ms 11208 KB Output is correct
13 Correct 87 ms 11316 KB Output is correct
14 Correct 89 ms 11192 KB Output is correct
15 Correct 3 ms 4940 KB Output is correct
16 Correct 4 ms 4940 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 4 ms 4940 KB Output is correct
19 Correct 4 ms 4940 KB Output is correct
20 Correct 11 ms 5068 KB Output is correct
21 Correct 232 ms 7876 KB Output is correct
22 Correct 5 ms 5004 KB Output is correct
23 Correct 11 ms 5068 KB Output is correct
24 Correct 218 ms 7896 KB Output is correct
25 Correct 167 ms 7776 KB Output is correct
26 Correct 205 ms 8004 KB Output is correct
27 Correct 247 ms 7848 KB Output is correct
28 Correct 3063 ms 8152 KB Output is correct
29 Execution timed out 4019 ms 11332 KB Time limit exceeded
30 Halted 0 ms 0 KB -