oj.uz

Submission #444163

# Submission time Handle Problem Language Result Execution time Memory
444163 2021-07-13T08:17:31 Z peijar Comparing Plants (IOI20_plants) C++17
49 / 100
 581 ms 25436 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 : 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;

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

  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 (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
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 59 ms 7744 KB Output is correct
7 Correct 68 ms 8204 KB Output is correct
8 Correct 92 ms 11212 KB Output is correct
9 Correct 91 ms 11220 KB Output is correct
10 Correct 92 ms 11188 KB Output is correct
11 Correct 90 ms 11204 KB Output is correct
12 Correct 91 ms 11180 KB Output is correct
13 Correct 90 ms 11176 KB Output is correct
14 Correct 92 ms 11212 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4964 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 4 ms 4940 KB Output is correct
6 Correct 6 ms 5068 KB Output is correct
7 Correct 74 ms 8164 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 6 ms 5068 KB Output is correct
10 Correct 70 ms 7932 KB Output is correct
11 Correct 66 ms 7924 KB Output is correct
12 Correct 68 ms 8056 KB Output is correct
13 Correct 69 ms 8040 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4964 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 4 ms 4940 KB Output is correct
6 Correct 6 ms 5068 KB Output is correct
7 Correct 74 ms 8164 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 6 ms 5068 KB Output is correct
10 Correct 70 ms 7932 KB Output is correct
11 Correct 66 ms 7924 KB Output is correct
12 Correct 68 ms 8056 KB Output is correct
13 Correct 69 ms 8040 KB Output is correct
14 Correct 100 ms 8900 KB Output is correct
15 Correct 581 ms 21356 KB Output is correct
16 Correct 100 ms 11204 KB Output is correct
17 Correct 542 ms 24984 KB Output is correct
18 Correct 351 ms 24600 KB Output is correct
19 Correct 342 ms 25140 KB Output is correct
20 Correct 534 ms 25068 KB Output is correct

Subtask #4
17.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 Correct 66 ms 7884 KB Output is correct
4 Correct 283 ms 25436 KB Output is correct
5 Correct 330 ms 24496 KB Output is correct
6 Correct 430 ms 24608 KB Output is correct
7 Correct 517 ms 24852 KB Output is correct
8 Correct 559 ms 24884 KB Output is correct
9 Correct 299 ms 24368 KB Output is correct
10 Correct 296 ms 24372 KB Output is correct
11 Correct 89 ms 14144 KB Output is correct
12 Correct 278 ms 24332 KB Output is correct
13 Correct 348 ms 24400 KB Output is correct

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 Correct 3 ms 4940 KB Output is correct
5 Incorrect 3 ms 4940 KB Output isn't correct
6 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 4 ms 4940 KB Output is correct
4 Incorrect 3 ms 4940 KB Output isn't correct
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 59 ms 7744 KB Output is correct
7 Correct 68 ms 8204 KB Output is correct
8 Correct 92 ms 11212 KB Output is correct
9 Correct 91 ms 11220 KB Output is correct
10 Correct 92 ms 11188 KB Output is correct
11 Correct 90 ms 11204 KB Output is correct
12 Correct 91 ms 11180 KB Output is correct
13 Correct 90 ms 11176 KB Output is correct
14 Correct 92 ms 11212 KB Output is correct
15 Correct 3 ms 4964 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 4 ms 4940 KB Output is correct
20 Correct 6 ms 5068 KB Output is correct
21 Correct 74 ms 8164 KB Output is correct
22 Correct 5 ms 5068 KB Output is correct
23 Correct 6 ms 5068 KB Output is correct
24 Correct 70 ms 7932 KB Output is correct
25 Correct 66 ms 7924 KB Output is correct
26 Correct 68 ms 8056 KB Output is correct
27 Correct 69 ms 8040 KB Output is correct
28 Correct 100 ms 8900 KB Output is correct
29 Correct 581 ms 21356 KB Output is correct
30 Correct 100 ms 11204 KB Output is correct
31 Correct 542 ms 24984 KB Output is correct
32 Correct 351 ms 24600 KB Output is correct
33 Correct 342 ms 25140 KB Output is correct
34 Correct 534 ms 25068 KB Output is correct
35 Correct 3 ms 4940 KB Output is correct
36 Correct 3 ms 4940 KB Output is correct
37 Correct 66 ms 7884 KB Output is correct
38 Correct 283 ms 25436 KB Output is correct
39 Correct 330 ms 24496 KB Output is correct
40 Correct 430 ms 24608 KB Output is correct
41 Correct 517 ms 24852 KB Output is correct
42 Correct 559 ms 24884 KB Output is correct
43 Correct 299 ms 24368 KB Output is correct
44 Correct 296 ms 24372 KB Output is correct
45 Correct 89 ms 14144 KB Output is correct
46 Correct 278 ms 24332 KB Output is correct
47 Correct 348 ms 24400 KB Output is correct
48 Correct 3 ms 4940 KB Output is correct
49 Correct 3 ms 4940 KB Output is correct
50 Correct 3 ms 4940 KB Output is correct
51 Correct 3 ms 4940 KB Output is correct
52 Incorrect 3 ms 4940 KB Output isn't correct
53 Halted 0 ms 0 KB -