Submission #444154

#	Time	Username	Problem	Language	Result	Execution time	Memory
444154		peijar	Comparing Plants (IOI20_plants)	C++17	30 / 100	4083 ms	14152 KiB

plants

#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 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 11 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25