Submission #1189653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189653		Clan328	모자이크 (IOI24_mosaic)	C++20	41 / 100	1096 ms	30128 KiB

mosaic

#include "mosaic.h"

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define nL '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y,
                              std::vector<int> T, std::vector<int> B,
                              std::vector<int> L, std::vector<int> R) {
  int Q = (int)T.size();
  std::vector<long long> C(Q, 0);
  int N = (int)X.size();

  if (N <= 3) {
    vvi mat(N, vi(N));
    mat[0] = X;
    for (int i = 0; i < N; i++) mat[i][0] = Y[i];

    for (int i = 1; i < N; i++) {
        for (int j = 1; j < N; j++) {
            mat[i][j] = mat[i-1][j] == 0 && mat[i][j-1] == 0;
        }
    }

    for (int i = 0; i < Q; i++) {
        for (int j = T[i]; j <= B[i]; j++) {
            for (int k = L[i]; k <= R[i]; k++) {
                C[i] += mat[j][k];
            }
        }
    }

    return C;
  }

    // vvi mat(N, vi(N));
    // mat[0] = X;
    // for (int i = 0; i < N; i++) mat[i][0] = Y[i];

    // for (int i = 1; i < N; i++) {
    //     for (int j = 1; j < N; j++) {
    //         if (j >= 3 && i > 2) break;
    //         mat[i][j] = mat[i-1][j] == 0 && mat[i][j-1] == 0;
    //     }
    // }

    // for (int i = 3; i < N; i++) {
    //     for (int j = 3; j < N; j++) {
    //         int d = min(i-3+1, j-3+1);
    //         mat[i][j] = mat[i-d][j-d];
    //     }
    // }

    // for (int i = 0; i < Q; i++) {
    //     for (int j = T[i]; j <= B[i]; j++) {
    //         for (int k = L[i]; k <= R[i]; k++) {
    //             C[i] += mat[j][k];
    //         }
    //     }
    // }

    // return C;

  // N > 3
  vvi mat(N);
  for (int i = 0; i < 3; i++) mat[i] = vi(N);
  for (int i = 3; i < N; i++) mat[i] = vi(3);

  mat[0] = X;
  for (int i = 0; i < N; i++) mat[i][0] = Y[i];

  for (int i = 1; i < N; i++) {
    for (int j = 1; j < mat[i].size(); j++) {
        mat[i][j] = mat[i-1][j] == 0 && mat[i][j-1] == 0;
    }
  }

  vvi sumCol(3, vi(N)), sumRow(3, vi(N));
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < N; j++) {
        sumCol[i][j] = (j > 0? sumCol[i][j-1] : 0) + mat[j][i];
    }
  }
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < N; j++) {
        sumRow[i][j] = (j > 0? sumRow[i][j-1] : 0) + mat[i][j];
    }
  }

  for (int i = 0; i < Q; i++) {
    while (L[i] <= R[i] && L[i] < 3) {
        C[i] += sumCol[L[i]][B[i]]-(T[i] > 0? sumCol[L[i]][T[i]-1] : 0);
        L[i]++;
    }
    if (L[i] > R[i]) continue;
    while (T[i] <= B[i] && T[i] < 3) {
        C[i] += sumRow[T[i]][R[i]]-(L[i] > 0? sumRow[T[i]][L[i]-1] : 0);
        T[i]++;
    }
    if (T[i] > B[i]) continue;
    
    for (int j = T[i]; j <= B[i]; j++) {
        for (int k = L[i]; k <= R[i]; k++) {
            int d = min(j-3+1, k-3+1);
            C[i] += mat[j-d][k-d];
        }
    }
  }

  return C;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 8
• Subtask 6: 22 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22