Submission #441649

#	Time	Username	Problem	Language	Result	Execution time	Memory
441649		peijar	Rectangles (IOI19_rect)	C++17	0 / 100	4 ms	1484 KiB

rect

#include "rect.h"
#include <algorithm>
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 2500 * 2500;

int id[MAXN];
int sz[MAXN];
int minLig[MAXN], maxLig[MAXN], minCol[MAXN], maxCol[MAXN];
bool activated[2500][2500];
int DX[] = {-1, 1, 0, 0};
int DY[] = {0, 0, -1, 1};
int nbLig, nbCol;
set<tuple<int, int, int, int>> rectangles, curRectangles;

int find(int i) {
  if (id[i] == i)
    return i;
  return id[i] = find(id[i]);
}

bool estRectangle(int cc) {
  assert(id[cc] == cc);
  return minLig[cc] > 0 and maxLig[cc] < nbLig - 1 and minCol[cc] > 0 and
         maxCol[cc] < nbCol - 1 and
         sz[cc] ==
             (1 + maxCol[cc] - minCol[cc]) * (maxLig[cc] - minLig[cc] + 1);
}

void merge(int a, int b) {
  a = find(a);
  b = find(b);
  if (a == b)
    return;
  if (sz[a] < sz[b])
    swap(a, b);
  if (estRectangle(a)) {
    curRectangles.erase({minLig[a], maxLig[a], minCol[a], maxCol[a]});
  }
  if (estRectangle(b)) {
    curRectangles.erase({minLig[b], maxLig[b], minCol[b], maxCol[b]});
  }
  id[b] = a;
  sz[a] += sz[b];
  minLig[a] = min(minLig[a], minLig[b]);
  maxLig[a] = max(maxLig[a], maxLig[b]);
  minCol[a] = min(minCol[a], minCol[b]);
  maxCol[a] = max(maxCol[a], maxCol[b]);
  if (estRectangle(a)) {
    curRectangles.insert({minLig[a], maxLig[a], minCol[a], maxCol[a]});
  }
}

int hashCoord(int iLig, int iCol) { return iLig * nbCol + iCol; }

void active(int iLig, int iCol) {
  int hsh = hashCoord(iLig, iCol);
  id[hsh] = hsh;
  sz[hsh] = 1;
  minLig[hsh] = maxLig[hsh] = iLig;
  minCol[hsh] = maxCol[hsh] = iCol;
  if (estRectangle(hsh))
    curRectangles.insert({iLig, iLig, iCol, iCol});
}

int count_rectangles(vector<vector<signed>> a) {
  vector<int> vals;
  nbLig = a.size(), nbCol = a[0].size();

  for (int iLig = 0; iLig < nbLig; ++iLig)
    for (int iCol = 0; iCol < nbCol; ++iCol)
      vals.push_back(a[iLig][iCol]);
  sort(vals.begin(), vals.end());
  vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
  for (int iLig = 0; iLig < nbLig; ++iLig)
    for (int iCol = 0; iCol < nbCol; ++iCol)
      a[iLig][iCol] =
          lower_bound(vals.begin(), vals.end(), a[iLig][iCol]) - vals.begin();
  for (int iLig = 0; iLig < nbLig; ++iLig)
    for (int iCol = 0; iCol < nbCol; ++iCol)
      cout << a[iLig][iCol] << " \n"[iCol == nbCol - 1];

  int nbVal = vals.size();
  vector<vector<pair<int, int>>> withVal(nbVal);
  for (int iLig = 0; iLig < nbLig; ++iLig)
    for (int iCol = 0; iCol < nbCol; ++iCol)
      withVal[a[iLig][iCol]].emplace_back(iLig, iCol);
  for (int val = 0; val < nbVal; ++val) {
    for (auto [iLig, iCol] : withVal[val]) {
      active(iLig, iCol);
      activated[iLig][iCol] = true;
    }
    for (auto [iLig, iCol] : withVal[val]) {
      for (int d = 0; d < 4; ++d) {
        int lig = iLig + DX[d];
        int col = iCol + DY[d];
        if (lig < 0 or col < 0 or lig >= nbLig or col >= nbCol or
            !activated[lig][col])
          continue;
        merge(hashCoord(iLig, iCol), hashCoord(lig, col));
      }
    }
    // cout << val << ' ' << curRectangles.size() << endl;
    for (auto v : curRectangles)
      rectangles.insert(v);
  }
  return rectangles.size();
  ;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28