제출 #442213

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442213		peijar	Vision Program (IOI19_vision)	C++17	32 / 100	14 ms	4664 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 maxDeltaLig = nbLig - 1;
  vector<int> avecDeltaLig(maxDeltaLig + 1);

  // 2 sur meme lig ?
  vector<int> sameLig;
  for (int lig = 0; lig < nbLig; ++lig) {
    vector<int> pos;
    for (int col = 0; col < nbCol; ++col)
      pos.push_back(col + nbCol * lig);
    sameLig.push_back(add_and({add_or(pos), add_not(add_xor(pos))}));
  }
  avecDeltaLig[0] = add_or(sameLig);
  vector<int> before;
  before.push_back(avecDeltaLig[0]);

  for (int deltaLig = maxDeltaLig; deltaLig; --deltaLig) {
    if (nbLig - deltaLig <= deltaLig) {
      vector<int> toAsk;
      for (int lig = 0; lig + deltaLig < nbLig; ++lig) {
        vector<int> cases1, cases2;
        for (int col = 0; col < nbCol; ++col)
          cases1.push_back(col + nbCol * lig),
              cases2.push_back(col + nbCol * (lig + deltaLig));
        toAsk.push_back(add_and({add_or(cases1), add_or(cases2)}));
      }
      avecDeltaLig[deltaLig] = add_or(toAsk);
    } else {
      vector<int> toAsk;
      for (int residu = 0; residu < deltaLig; ++residu) {
        vector<int> cases;
        for (int lig = residu; lig < nbLig; lig += deltaLig)
          for (int col = 0; col < nbCol; ++col)
            cases.push_back(lig * nbCol + col);
        toAsk.push_back(add_and({add_or(cases), add_not(add_xor(cases))}));
      }
      int withMult = add_or(toAsk);
      avecDeltaLig[deltaLig] = add_and({withMult, add_not(add_or(before))});
    }
    before.push_back(avecDeltaLig[deltaLig]);
  }

  int maxDeltaCol = nbCol - 1;
  vector<int> avecDeltaCol(maxDeltaCol + 1);

  vector<int> sameCol;
  for (int col = 0; col < nbCol; ++col) {
    vector<int> pos;
    for (int lig = 0; lig < nbLig; ++lig)
      pos.push_back(col + nbCol * lig);
    sameCol.push_back(add_and({add_or(pos), add_not(add_xor(pos))}));
  }

  avecDeltaCol[0] = add_or(sameCol);
  before.clear();
  before.push_back(avecDeltaCol[0]);
  for (int deltaCol = maxDeltaCol; deltaCol; --deltaCol) {
    if (nbCol - deltaCol <= deltaCol) {
      vector<int> toAsk;
      for (int col = 0; col + deltaCol < nbCol; ++col) {
        vector<int> pos1, pos2;
        for (int lig = 0; lig < nbLig; ++lig)
          pos1.push_back(col + nbCol * lig),
              pos2.push_back(col + deltaCol + nbCol * lig);
        toAsk.push_back(add_and({add_or(pos1), add_or(pos2)}));
      }
      avecDeltaCol[deltaCol] = add_or(toAsk);
    } else {
      vector<int> toAsk;
      for (int residu = 0; residu < deltaCol; ++residu) {
        vector<int> cases;
        for (int col = residu; col < nbCol; col += deltaCol)
          for (int lig = 0; lig < nbLig; ++lig)
            cases.push_back(col + nbCol * lig);
        toAsk.push_back(add_and({add_or(cases), add_not(add_xor(cases))}));
      }
      int withMult = add_or(toAsk);
      avecDeltaCol[deltaCol] = add_and({withMult, add_not(add_or(before))});
    }
    before.push_back(avecDeltaCol[deltaCol]);
  }

  vector<int> q;
  for (int dL = 0; dL <= maxDeltaLig; ++dL) {
    int dC = K - dL;
    if (dC >= 0 and dC <= maxDeltaCol)
      q.push_back(add_and({avecDeltaCol[dC], avecDeltaLig[dL]}));
  }
  add_or(q);
}

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