Submission #541641

#	Time	Username	Problem	Language	Result	Execution time	Memory
541641		abeker	Vision Program (IOI19_vision)	C++17	100 / 100	18 ms	1772 KiB

vision

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

//-1 = FALSE, -2 = TRUE

const int B = 15;

int my_add_or(vector <int> v) {
  vector <int> tmp;
  for (auto it : v)
    if (it >= 0)
      tmp.push_back(it);
    else if (it == -2)
      return -2;
  return tmp.empty() ? -1 : add_or(tmp);
}

int my_add_and(vector <int> v) {
  vector <int> tmp;
  for (auto it : v)
    if (it >= 0)
      tmp.push_back(it);
    else if (it == -1)
      return -1;
  return tmp.empty() ? -2 : add_and(tmp);
}

int my_add_not(int x) {
  if (x < 0)
    return -3 - x;
  return add_not(x);
}

int my_add_nor(vector <int> v) {
  return my_add_not(my_add_or(v));
}

vector <int> solve(vector <int> a) {
  int N = a.size();
  vector <vector <int>> pref(B);
  for (int i = 0; i < N; i++)
    pref[i % B].push_back(i < B ? a[i] : my_add_or({pref[i % B].back(), a[i]}));
  vector <int> inv;
  vector <vector <int>> residue_pair(B, vector <int> (B));
  for (int i = 0; i < B; i++)
    for (int j = 0; j < B; j++)
      if (i != j) {
        int cnt = 0;
        vector <int> tmp;
        for (int k = 0; k < N; k++) {
          if (k % B == j && cnt)
            tmp.push_back(my_add_and({pref[i][cnt - 1], a[k]}));
          if (k % B == i)
            cnt++;
        }
        residue_pair[i][j] = my_add_or(tmp);
        if (i > j)
          inv.push_back(residue_pair[i][j]);
      }
  for (int i = 0; i < B; i++) {
    vector <int> tmp;
    for (int j = 0; j < B; j++)
      if (j != i && !pref[j].empty())
        tmp.push_back(pref[j].back());
    residue_pair[i][i] = my_add_nor(tmp);
  }
  vector <int> block(B);
  for (int i = 0; i < B; i++) {
    vector <int> tmp;
    for (int j = 0; j < B; j++)
      if (i * B + j < N)
        tmp.push_back(a[i * B + j]);
    block[i] = my_add_or(tmp);
  }
  vector <vector <int>> block_pair(B, vector <int> (B));
  for (int i = 0; i < B - 1; i++)
    for (int j = i + 1; j < B; j++)
      block_pair[i][j] = my_add_and({block[i], block[j]});
  for (int i = 0; i < B; i++) {
    vector <int> tmp;
    for (int j = 0; j < B; j++)
      if (j != i)
        tmp.push_back(block[j]);
    block_pair[i][i] = my_add_nor(tmp);
  }
  int carry = my_add_or(inv);
  int no_carry = my_add_not(carry);
  vector <int> residue_diff(B);
  for (int i = 0; i < B; i++) {
    vector <int> tmp;
    for (int j = 0; j < B; j++)
      tmp.push_back(residue_pair[j][(i + j) % B]);
    residue_diff[i] = my_add_or(tmp);
  }
  vector <int> block_diff(B);
  for (int i = 0; i < B; i++) {
    vector <int> option1, option2;
    for (int j = 0; j < B - i; j++) {
      option1.push_back(block_pair[j][i + j]);
      if (j < B - i - 1)
        option2.push_back(block_pair[j][i + j + 1]);
    }
    block_diff[i] = my_add_or({my_add_and({my_add_or(option1), no_carry}), my_add_and({my_add_or(option2), carry})});
  }
  vector <int> res(N);
  for (int i = 0; i < N; i++)
    res[i] = my_add_and({block_diff[i / B], residue_diff[i % B]});
  return res;
}

void construct_network(int H, int W, int K) {
  vector <int> row(H);
  for (int i = 0; i < H; i++) {
    vector <int> tmp(W);
    for (int j = 0; j < W; j++)
      tmp[j] = i * W + j;
    row[i] = my_add_or(tmp);
  }
  vector <int> col(W);
  for (int j = 0; j < W; j++) {
    vector <int> tmp(H);
    for (int i = 0; i < H; i++)
      tmp[i] = i * W + j;
    col[j] = my_add_or(tmp);
  }
  vector <int> combs;
  vector <int> row_diff = solve(row);
  vector <int> col_diff = solve(col);
  for (int i = 0; i <= K; i++)
    if (i < H && K - i < W)
      combs.push_back(my_add_and({row_diff[i], col_diff[K - i]}));
  my_add_or(combs);
}

• 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