oj.uz

Submission #443967

# Submission time Handle Problem Language Result Execution time Memory
443967 2021-07-12T16:29:34 Z peijar Comparing Plants (IOI20_plants) C++17
30 / 100
 4000 ms 11568 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;
        int x = pot[potAvant], y = pot[iPot];
        if (potAvant == iPot or disCircle(x, y) >= k)
          possibles.push_back(y);
      }

      /*cout << "Potentiels ";
      for (int i : pot)
        cout << i << ' ';
      cout << endl;
      cout << "Possibles ";
      for (int i : possibles)
        cout << i << ' ';
      cout << endl;*/

      assert(!possibles.empty());

      for (int iPlante : possibles) {
        for (int j = 0; j < nbPlantes; ++j) {
          if (disCircle(j, iPlante) < k and !seen[j]) {
            nbDevant[j]--;
            adj[iPlante].push_back(j);
            // cout << "Edge " << iPlante << ' ' << j << endl;
          }
        }
        seen[iPlante] = true;
        nbRestant--;
      }
      for (int iPlante : possibles)
        for (int j = 0; j < nbPlantes; ++j)
          if (disCircle(iPlante, j) < k and !seen[j]) {
            // cout << "Edge " << iPlante << ' ' << j << endl;
            adj[iPlante].push_back(j);
          }
    }

    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 5000 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 4940 KB Output is correct
6 Correct 57 ms 8004 KB Output is correct
7 Correct 67 ms 8360 KB Output is correct
8 Correct 95 ms 11460 KB Output is correct
9 Correct 104 ms 11568 KB Output is correct
10 Correct 89 ms 11460 KB Output is correct
11 Correct 92 ms 11460 KB Output is correct
12 Correct 88 ms 11460 KB Output is correct
13 Correct 85 ms 11440 KB Output is correct
14 Correct 88 ms 11460 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 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 11 ms 5068 KB Output is correct
7 Correct 232 ms 8100 KB Output is correct
8 Correct 5 ms 5016 KB Output is correct
9 Correct 11 ms 5068 KB Output is correct
10 Correct 225 ms 8104 KB Output is correct
11 Correct 166 ms 8104 KB Output is correct
12 Correct 198 ms 8412 KB Output is correct
13 Correct 240 ms 8104 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 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 11 ms 5068 KB Output is correct
7 Correct 232 ms 8100 KB Output is correct
8 Correct 5 ms 5016 KB Output is correct
9 Correct 11 ms 5068 KB Output is correct
10 Correct 225 ms 8104 KB Output is correct
11 Correct 166 ms 8104 KB Output is correct
12 Correct 198 ms 8412 KB Output is correct
13 Correct 240 ms 8104 KB Output is correct
14 Correct 2983 ms 8412 KB Output is correct
15 Execution timed out 4075 ms 11460 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 5008 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Execution timed out 4098 ms 9788 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
11.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 4 ms 4940 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 19 ms 5964 KB Output is correct
8 Correct 43 ms 6124 KB Output is correct
9 Correct 22 ms 5964 KB Output is correct
10 Correct 41 ms 6124 KB Output is correct
11 Correct 21 ms 5964 KB Output is correct
12 Correct 24 ms 5992 KB Output is correct
13 Correct 16 ms 5996 KB Output is correct

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 Correct 3 ms 5012 KB Output is correct
5 Incorrect 805 ms 5904 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5000 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 4940 KB Output is correct
6 Correct 57 ms 8004 KB Output is correct
7 Correct 67 ms 8360 KB Output is correct
8 Correct 95 ms 11460 KB Output is correct
9 Correct 104 ms 11568 KB Output is correct
10 Correct 89 ms 11460 KB Output is correct
11 Correct 92 ms 11460 KB Output is correct
12 Correct 88 ms 11460 KB Output is correct
13 Correct 85 ms 11440 KB Output is correct
14 Correct 88 ms 11460 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 3 ms 4940 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 11 ms 5068 KB Output is correct
21 Correct 232 ms 8100 KB Output is correct
22 Correct 5 ms 5016 KB Output is correct
23 Correct 11 ms 5068 KB Output is correct
24 Correct 225 ms 8104 KB Output is correct
25 Correct 166 ms 8104 KB Output is correct
26 Correct 198 ms 8412 KB Output is correct
27 Correct 240 ms 8104 KB Output is correct
28 Correct 2983 ms 8412 KB Output is correct
29 Execution timed out 4075 ms 11460 KB Time limit exceeded
30 Halted 0 ms 0 KB -