oj.uz

Submission #444165

# Submission time Handle Problem Language Result Execution time Memory
444165 2021-07-13T08:27:52 Z peijar Comparing Plants (IOI20_plants) C++17
15 / 100
 1262 ms 41400 KB 
#include "plants.h"
#include <bits/stdc++.h>
#include <type_traits>
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 : AC
 * 4 : AC
 * 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];
set<int> alwaysSmaller, alwaysBigger;
int nbPlantes;

struct Seg {
  int nbValeurs;
  vector<int> order;
  vector<int> valeurs;
  vector<int> iDeb, iFin, lazy, minVal;
  const int INF = 1e9;

  Seg(vector<int> _v) : nbValeurs(_v.size()), valeurs(_v) {
    int p = 0;
    while ((1 << p) < nbValeurs)
      ++p;
    int x = 2 * (1 << p) + 1;
    iDeb.resize(x), iFin.resize(x), lazy.resize(x), minVal.resize(x);
    buildTree(1, 0, nbValeurs - 1);
  }

  void pull(int iNoeud) {
    minVal[iNoeud] = min(minVal[2 * iNoeud], minVal[2 * iNoeud + 1]);
  }

  void push(int iNoeud) {
    if (!lazy[iNoeud])
      return;
    minVal[iNoeud] += lazy[iNoeud];
    if (iDeb[iNoeud] < iFin[iNoeud]) {
      lazy[2 * iNoeud] += lazy[iNoeud];
      lazy[2 * iNoeud + 1] += lazy[iNoeud];
    }
    lazy[iNoeud] = 0;
  }

  void buildTree(int iNoeud, int deb, int fin) {
    iDeb[iNoeud] = deb, iFin[iNoeud] = fin;
    if (deb == fin) {
      minVal[iNoeud] = valeurs[deb];
      return;
    }
    buildTree(2 * iNoeud, deb, (deb + fin) / 2);
    buildTree(2 * iNoeud + 1, (deb + fin) / 2 + 1, fin);
    pull(iNoeud);
  }

  int queryMin(int iNoeud, int deb, int fin) {
    push(iNoeud);
    if (deb > iFin[iNoeud] or fin < iDeb[iNoeud])
      return 2 * INF;
    if (iDeb[iNoeud] >= deb and iFin[iNoeud] <= fin)
      return minVal[iNoeud];
    return min(queryMin(2 * iNoeud, deb, fin),
               queryMin(2 * iNoeud + 1, deb, fin));
  }

  void decrement(int iNoeud, int deb, int fin) {
    push(iNoeud);
    if (deb > iFin[iNoeud] or fin < iDeb[iNoeud])
      return;
    if (deb <= iDeb[iNoeud] and iFin[iNoeud] <= fin) {
      lazy[iNoeud]--;
      push(iNoeud);
      return;
    }
    decrement(2 * iNoeud, deb, fin);
    decrement(1 + 2 * iNoeud, deb, fin);
    pull(iNoeud);
  }

  int findFirstZero(int iNoeud, int deb, int fin) {
    push(iNoeud);
    if (minVal[iNoeud] or iDeb[iNoeud] > fin or iFin[iNoeud] < deb)
      return -1;
    if (iDeb[iNoeud] == iFin[iNoeud])
      return iDeb[iNoeud];
    int retLft = findFirstZero(2 * iNoeud, deb, fin);
    if (retLft != -1)
      return retLft;
    return findFirstZero(2 * iNoeud + 1, deb, fin);
  }

  void delVal(int iNoeud, int pos) {
    push(iNoeud);
    if (iDeb[iNoeud] > pos or iFin[iNoeud] < pos)
      return;
    if (iDeb[iNoeud] == iFin[iNoeud]) {
      minVal[iNoeud] = INF;
      return;
    }
    delVal(2 * iNoeud, pos);
    delVal(2 * iNoeud + 1, pos);
    pull(iNoeud);
  }

  int findZeroBefore(int pos) {
    int posAvant = pos - k + 1;
    if (posAvant >= 0)
      return findFirstZero(1, posAvant, pos - 1);
    else {
      posAvant += nbValeurs;
      int ret = findFirstZero(1, posAvant, nbValeurs - 1);
      if (ret == -1 and pos)
        ret = findFirstZero(1, 0, pos - 1);
      return ret;
    }
  }

  void get(int pos) {
    // cout << "EXTRACTING " << pos << endl;
    while (true) {
      int x = findZeroBefore(pos);
      if (x == -1)
        break;
      get(x);
    }
    order.push_back(pos);
    int posAvant = pos - k + 1;
    delVal(1, pos);
    if (pos)
      decrement(1, max(0, posAvant), pos - 1);
    if (posAvant < 0)
      decrement(1, posAvant + nbValeurs, nbValeurs - 1);
    // cout << "EXTRACTED " << pos << endl;
  }

  void getNxt() {
    /*cout << "FINDING NEXT : " << endl;
    for (int i = 0; i < nbValeurs; ++i)
      cout << queryMin(1, i, i) << ' ';
    cout << endl;*/
    int posZero = findFirstZero(1, 0, nbValeurs - 1);
    assert(posZero != -1);
    get(posZero);
  }
};

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];
  }

  Seg segMax(r);
  while ((int)segMax.order.size() < nbPlantes)
    segMax.getNxt();
  for (int i = 0; i < nbPlantes; ++i)
    r[i] = k - 1 - r[i];
  Seg segMin(r);
  while ((int)segMin.order.size() < nbPlantes)
    segMin.getNxt();
  for (int i = 0; i < nbPlantes and segMax.order[i]; ++i)
    alwaysBigger.insert(segMax.order[i]);
  for (int i = 0; i < nbPlantes and segMin.order[i]; ++i)
    alwaysSmaller.insert(segMin.order[i]);

  /*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 {
    Seg seg(r);
    while ((int)seg.order.size() < nbPlantes)
      seg.getNxt();
    for (int i = 0; i < nbPlantes; ++i)
      ordre[seg.order[i]] = nbPlantes - 1 - i;
  }*/
}

int compare_plants(int x, int y) {
  if (alwaysBigger.count(y))
    return -1;
  if (alwaysSmaller.count(y))
    return 1;
  return 0;
  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
    return (ordre[x] < ordre[y] ? -1 : 1);
}

Subtask #1
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 Incorrect 3 ms 4940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 3 ms 4940 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 Incorrect 3 ms 4940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct
2 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 Incorrect 3 ms 4940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
15.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 4968 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 5 ms 5068 KB Output is correct
6 Correct 598 ms 32728 KB Output is correct
7 Correct 980 ms 39348 KB Output is correct
8 Correct 1136 ms 41308 KB Output is correct
9 Correct 1262 ms 41400 KB Output is correct
10 Correct 520 ms 32832 KB Output is correct
11 Correct 892 ms 41072 KB Output is correct
12 Correct 619 ms 39472 KB Output is correct
13 Correct 623 ms 33460 KB Output is correct
14 Correct 977 ms 40208 KB Output is correct
15 Correct 1113 ms 41268 KB Output is correct
16 Correct 597 ms 39188 KB Output is correct
17 Correct 590 ms 34176 KB Output is correct

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 Incorrect 3 ms 4940 KB Output isn't correct
4 Halted 0 ms 0 KB -