oj.uz

Submission #444154

# Submission time Handle Problem Language Result Execution time Memory
444154 2021-07-13T07:36:29 Z peijar Comparing Plants (IOI20_plants) C++17
30 / 100
 4000 ms 14152 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]
 * 1 : AC
 * 2 : AC
 * 3 : NA
 * 4 : NA
 * 5 : AC
 * 6 : NA
 * 7 : NA
 *
 * If can build graph efficiently then ez !
 */

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)
      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 nbPlusGrands[iPlante] == 0)
          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] = nbPlantes - iOrdre - 1;
      for (int iPlante = 0; iPlante < nbPlantes; ++iPlante)
        if (disCircle(iPlante, x) < k and ordre[iPlante] == -1)
          nbPlusGrands[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);
      }

      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);
          }
        }
        seen[iPlante] = true;
        nbRestant--;
      }
      for (int iPlante : possibles)
        for (int j = 0; j < nbPlantes; ++j)
          if (disCircle(iPlante, j) < k and !seen[j]) {
            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 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5004 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 5012 KB Output is correct
6 Correct 57 ms 8756 KB Output is correct
7 Correct 70 ms 10372 KB Output is correct
8 Correct 92 ms 14148 KB Output is correct
9 Correct 92 ms 14132 KB Output is correct
10 Correct 91 ms 14152 KB Output is correct
11 Correct 90 ms 14116 KB Output is correct
12 Correct 89 ms 14140 KB Output is correct
13 Correct 87 ms 14120 KB Output is correct
14 Correct 86 ms 14140 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 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 5004 KB Output is correct
6 Correct 11 ms 5068 KB Output is correct
7 Correct 244 ms 9792 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 11 ms 5124 KB Output is correct
10 Correct 239 ms 9924 KB Output is correct
11 Correct 207 ms 9660 KB Output is correct
12 Correct 176 ms 9920 KB Output is correct
13 Correct 251 ms 9712 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 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 5004 KB Output is correct
6 Correct 11 ms 5068 KB Output is correct
7 Correct 244 ms 9792 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 11 ms 5124 KB Output is correct
10 Correct 239 ms 9924 KB Output is correct
11 Correct 207 ms 9660 KB Output is correct
12 Correct 176 ms 9920 KB Output is correct
13 Correct 251 ms 9712 KB Output is correct
14 Correct 3173 ms 10284 KB Output is correct
15 Execution timed out 4083 ms 13736 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 Correct 3 ms 4940 KB Output is correct
3 Execution timed out 4030 ms 9796 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 3 ms 5008 KB Output is correct
4 Correct 3 ms 5004 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 6004 KB Output is correct
8 Correct 40 ms 6160 KB Output is correct
9 Correct 23 ms 5964 KB Output is correct
10 Correct 38 ms 6128 KB Output is correct
11 Correct 21 ms 5964 KB Output is correct
12 Correct 24 ms 6000 KB Output is correct
13 Correct 17 ms 5964 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 4940 KB Output is correct
5 Incorrect 794 ms 5908 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 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5004 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 5012 KB Output is correct
6 Correct 57 ms 8756 KB Output is correct
7 Correct 70 ms 10372 KB Output is correct
8 Correct 92 ms 14148 KB Output is correct
9 Correct 92 ms 14132 KB Output is correct
10 Correct 91 ms 14152 KB Output is correct
11 Correct 90 ms 14116 KB Output is correct
12 Correct 89 ms 14140 KB Output is correct
13 Correct 87 ms 14120 KB Output is correct
14 Correct 86 ms 14140 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 4940 KB Output is correct
18 Correct 3 ms 4940 KB Output is correct
19 Correct 4 ms 5004 KB Output is correct
20 Correct 11 ms 5068 KB Output is correct
21 Correct 244 ms 9792 KB Output is correct
22 Correct 4 ms 5068 KB Output is correct
23 Correct 11 ms 5124 KB Output is correct
24 Correct 239 ms 9924 KB Output is correct
25 Correct 207 ms 9660 KB Output is correct
26 Correct 176 ms 9920 KB Output is correct
27 Correct 251 ms 9712 KB Output is correct
28 Correct 3173 ms 10284 KB Output is correct
29 Execution timed out 4083 ms 13736 KB Time limit exceeded
30 Halted 0 ms 0 KB -