Submission #442565

#	Time	Username	Problem	Language	Result	Execution time	Memory
442565		peijar	Vision Program (IOI19_vision)	C++17	100 / 100	58 ms	5340 KiB

vision

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

/*
 * Subtask 1 - 2 - 3 - 5 - 6 - 7  : AC = 66
 * Subtask 4 8
 */

void construct_network(int nbLig, int nbCol, int K) {

  int maxSum = nbLig - 1 + nbCol - 1;
  vector<int> orSum(maxSum + 1), xorSum(maxSum + 1);
  for (int sum = 0; sum <= maxSum; ++sum) {
    vector<int> cases;
    for (int lig = 0; lig < nbLig; ++lig) {
      int col = sum - lig;
      if (col >= nbCol or col < 0)
        continue;
      cases.push_back(nbCol * lig + col);
    }
    orSum[sum] = add_or(cases);
    xorSum[sum] = add_xor(cases);
  }

  // nbCol -1 + lig - col
  vector<int> orDiff(maxSum + 1), xorDiff(maxSum + 1);
  for (int diff = 0; diff <= maxSum; ++diff) {
    vector<int> cases;
    for (int lig = 0; lig < nbLig; ++lig) {
      int col = nbCol - 1 + lig - diff;
      if (col < 0 or col >= nbCol)
        continue;
      cases.push_back(nbCol * lig + col);
    }
    orDiff[diff] = add_or(cases);
    xorDiff[diff] = add_xor(cases);
  }

  auto sumLess = [&](int k) {
    vector<int> sumLessK;
    for (int sum = 0; sum + k <= maxSum; ++sum) {
      vector<int> ors, xors;
      for (int s = sum; s <= sum + k; ++s)
        ors.push_back(orSum[s]), xors.push_back(xorSum[s]);
      sumLessK.push_back(add_and({add_or(ors), add_not(add_xor(xors))}));
    }
    return add_or(sumLessK);
  };

  auto diffLess = [&](int k) {
    vector<int> diffLessK;
    for (int diff = 0; diff + k <= maxSum; ++diff) {
      vector<int> ors, xors;
      for (int d = diff; d <= diff + k; ++d)
        ors.push_back(orDiff[d]), xors.push_back(xorDiff[d]);
      diffLessK.push_back(add_and({add_or(ors), add_not(add_xor(xors))}));
    }
    return add_or(diffLessK);
  };

  if (K == 1)
    add_and({sumLess(K), diffLess(K)});
  else
    add_and({sumLess(K), diffLess(K),
             add_or({add_not(diffLess(K - 1)), add_not(sumLess(K - 1))})});
}

• 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