제출 #1244953

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1244953		kunzaZa183	Vision Program (IOI19_vision)	C++20	100 / 100	41 ms	7960 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
using namespace std;

void construct_network(int H, int W, int K) {

  auto ptoi = [&](int a, int b) { return a * W + b; };

  auto itop = [&](int x) { return make_pair(x / W, x % W); };

  map<int, vector<int>> add, mini;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      add[i + j].push_back(ptoi(i, j));
      mini[i - j].push_back(ptoi(i, j));
    }
  }

  vector<vector<int>> avvi, mvvi;
  for (auto a : add)
    avvi.push_back(a.second);
  for (auto a : mini)
    mvvi.push_back(a.second);

  vector<int> aor(H + W - 1), mor(H + W - 1);
  for (int i = 0; i < H + W - 1; i++)
    aor[i] = add_or(avvi[i]), mor[i] = add_or(mvvi[i]);

  auto has2 = [&](vector<int> vi) {
    int x = add_or(vi);
    int y = add_xor(vi);
    return add_xor({x, y});
  };

  vector<int> ahas2(avvi.size()), mhas2(mvvi.size());
  for (int i = 0; i < avvi.size(); i++) {
    ahas2[i] = add_xor({aor[i], add_xor(avvi[i])});
    mhas2[i] = add_xor({mor[i], add_xor(mvvi[i])});
  }

  vector<int> ares, mres;
  for (int i = 0; i + K < H + W - 1; i++) {
    vector<int> vi;
    for (int j = i; j <= i + K; j++) {
      vi.push_back(aor[j]);
    }

    vector<int> vi2 = {has2(vi)};
    for (int j = i; j <= i + K; j++) {
      vi2.push_back(ahas2[j]);
    }

    ares.push_back(add_or(vi2));
  }

  for (int i = 0; i + K < H + W - 1; i++) {
    vector<int> vi;
    for (int j = i; j <= i + K; j++) {
      vi.push_back(mor[j]);
    }

    vector<int> vi2 = {has2(vi)};
    for (int j = i; j <= i + K; j++) {
      vi2.push_back(mhas2[j]);
    }

    mres.push_back(add_or(vi2));
  }

  int sth1 = add_and({add_or(ares), add_or(mres)});

  ares.clear(), mres.clear();
  for (int i = 0; i + K - 1 < H + W - 1; i++) {
    vector<int> vi;
    for (int j = i; j <= i + K - 1; j++) {
      vi.push_back(aor[j]);
    }

    vector<int> vi2 = {has2(vi)};
    for (int j = i; j <= i + K - 1; j++) {
      vi2.push_back(ahas2[j]);
    }

    ares.push_back(add_or(vi2));
  }

  for (int i = 0; i + K - 1 < H + W - 1; i++) {
    vector<int> vi;
    for (int j = i; j <= i + K - 1; j++) {
      vi.push_back(mor[j]);
    }

    vector<int> vi2 = {has2(vi)};
    for (int j = i; j <= i + K - 1; j++) {
      vi2.push_back(mhas2[j]);
    }

    mres.push_back(add_or(vi2));
  }

  int sth2 = add_and({add_or(ares), add_or(mres)});

  add_xor({sth1, sth2});
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 15 / 15
• Subtask 5: 12 / 12
• Subtask 6: 8 / 8
• Subtask 7: 14 / 14
• Subtask 8: 19 / 19