oj.uz

답안 #204411

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
204411 2020-02-25T17:01:20 Z ADJA Rectangles (IOI19_rect) C++14
23 / 100
 640 ms 123068 KB 
#include "rect.h"
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
 
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
 
using namespace std;

const int MAXN = 2500;

int n, m;
int a[MAXN][MAXN];
int ok[MAXN][MAXN];
int mxc[MAXN];

int one[MAXN][MAXN], zero[MAXN][MAXN];

long long solveSix() {
  for (int j = m - 1; j >= 0; j--) {
    for (int i = 0; i < n; i++) {
      if (a[i][j] == 0) {
        one[i][j] = 0;
        zero[i][j] = 1 + zero[i][j + 1];
      } else {
        zero[i][j] = 0;
        one[i][j] = 1 + one[i][j + 1];
      }
    }
  }

  long long ans = 0;
  for (int j = 0; j + 1 < m; j++) {
    int prevOne = -1, mnZero = 123123, mxZero = -1;
    for (int i = 0; i < n; i++) {
      if (a[i][j] == 1 && one[i][j + 1] == 0) {
        mxZero = max(mxZero, zero[i][j + 1]);
        mnZero = min(mnZero, zero[i][j + 1]);
      } else {
        int curOne = one[i][j + 1];
        if (prevOne != -1 && mxZero != -1 && mxZero == mnZero) {
          int zeroLen = mnZero;
          if (j + zeroLen + 1 < m && prevOne >= zeroLen && curOne >= zeroLen) {
            ans++;
            // cerr << i << " " << j << endl;
          }
        }
        prevOne = curOne;
        mnZero = 123123, mxZero = -1;
      }
    }
  }

  return ans;
}

long long count_rectangles(std::vector<std::vector<int> > A) {
  n = sz(A); m = sz(A[0]);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      a[i][j] = A[i][j];
    }
  }

  bool isSix = true;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (a[i][j] > 1) {
        isSix = false;
      }
    }
  }
  if (isSix) {
    return solveSix();
  }

  long long ans = 0;
  vector<int> cols;
  for (int i = 0; i < m; i++) {
    cols.push_back(i);
  }
  random_shuffle(all(cols));

  for (int coli = 0; coli < max(800, m); coli++) {
    int col = cols[coli];
    if (col == m - 1) {
      continue;
    }
    for (int i = 0; i < n; i++) {
      for (int j = col; j < m; j++) {
        ok[i][j] = 0;
      }
    }
    for (int i = 0; i < n; i++) {
      int mx = -1;
      for (int j = col + 1; j < m; j++) {
        if (a[i][col] > mx && a[i][j] > mx) {
          ok[i][j] = 1;
        }
        if (a[i][j] > mx) {
          mx = a[i][j];
        }
      }
    }
    for (int i = 0; i < n; i++) {
      for (int j = col + 1; j < m; j++) {
        if (ok[i][j]) {
          ok[i][j] = 1 + ok[i - 1][j];
        }
      }
    }

    for (int row = 0; row + 1 < n; row++) {
      for (int j = col + 1; j < m; j++) {
        mxc[j] = -1;
      }
      for (int row2 = row + 1; row2 < n; row2++) {
        bool good = true;
        for (int col2 = col + 1; col2 + 1 < m; col2++) {
          if (!(a[row][col2] > mxc[col2] && a[row2][col2] > mxc[col2])) {
            good = false;
          }
          if (good && row2 - 1 > row && ok[row2 - 1][col2 + 1] >= row2 - row - 1) {
            ans++;
          }
          if (a[row2][col2] > mxc[col2]) {
            mxc[col2] = a[row2][col2];
          }
        }
      }
    }
  }

  return ans;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 504 KB Output is correct
2 Correct 38 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 57 ms 504 KB Output is correct
6 Correct 53 ms 504 KB Output is correct
7 Correct 53 ms 504 KB Output is correct
8 Correct 59 ms 504 KB Output is correct
9 Correct 55 ms 504 KB Output is correct
10 Correct 13 ms 376 KB Output is correct
11 Correct 29 ms 504 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 277 ms 59296 KB Output is correct
3 Correct 630 ms 122360 KB Output is correct
4 Correct 640 ms 123000 KB Output is correct
5 Correct 640 ms 123068 KB Output is correct
6 Correct 270 ms 60792 KB Output is correct
7 Correct 542 ms 119928 KB Output is correct
8 Correct 575 ms 122872 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 632 KB Output is correct
12 Correct 5 ms 632 KB Output is correct
13 Correct 5 ms 376 KB Output is correct

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -