Submission #259522

#	Time	Username	Problem	Language	Result	Execution time	Memory
259522		anayk	Vision Program (IOI19_vision)	C++14	100 / 100	20 ms	1480 KiB

vision

    #include "vision.h"
     
    void construct_network(int H, int W, int K) {
      std::vector<int> row(H, 0), col(W, 0);
     
      for(int i = 0; i < H; i++) {
        std::vector<int> cur;
        for(int j = 0; j < W; j++) {
          cur.push_back(i*W + j);
        }
        row[i] = add_or(cur);
      }
     
      for(int i = 0; i < W; i++) {
        std::vector<int> cur;
        for(int j = 0; j < H; j++) {
          cur.push_back(j*W + i);
        }
        col[i] = add_or(cur);
      }
     
      std::vector<int> spec = {19, 21, 23};
     
      std::vector<int> rows[spec.size()], cols[spec.size()];
      for(int i = 0; i < spec.size(); i++) {
        for(int j = 0; j < spec[i]; j++) {
          std::vector<int> cur;
          rows[i].push_back(-1);
          for(int k = j; k < H; k += spec[i])
            cur.push_back(row[k]);
          if(cur.size() == 0)
            continue;
          rows[i][j] = add_or(cur);
        }
      }
     
      for(int i = 0; i < spec.size(); i++) {
        for(int j = 0; j < spec[i]; j++) {
          std::vector<int> cur;
          cols[i].push_back(-1);
          for(int k = j; k < W; k += spec[i])
            cur.push_back(col[k]);
          if(cur.size() == 0)
            continue;
          cols[i][j] = add_or(cur);
        }
      }
     
      std::vector<int> mrows[spec.size()], mcols[spec.size()];
      for(int i = 0; i < spec.size(); i++) {
        std::vector<int> cur;
        for(int j = 0; j < spec[i]; j++)
          if(rows[i][j] > -1) cur.push_back(rows[i][j]);
        if(cur.size() != 0)
          mrows[i].push_back(add_xor(cur));
     
        for(int j = 1; j < spec[i]; j++) {
          std::vector<int> temp;
          for(int k = 0; k < spec[i]; k++) {
            if(rows[i][(k+j)%spec[i]] > -1 && rows[i][k] > -1) temp.push_back(add_and({rows[i][k], rows[i][(k+j)%spec[i]]}));
          }
          mrows[i].push_back(-1);
          if(temp.size() == 0)
            continue;
          mrows[i][j] = add_or(temp);
        }
      }
     
      for(int i = 0; i < spec.size(); i++) {
        std::vector<int> cur;
        for(int j = 0; j < spec[i]; j++)
          if(cols[i][j] > -1) cur.push_back(cols[i][j]);
        if(cur.size() != 0)
          mcols[i].push_back(add_xor(cur));
     
        for(int j = 1; j < spec[i]; j++) {
          std::vector<int> temp;
          for(int k = 0; k < spec[i]; k++) {
            if(cols[i][(k+j)%spec[i]] > -1 && cols[i][k] > -1) temp.push_back(add_and({cols[i][k], cols[i][(k+j)%spec[i]]}));
          }
          mcols[i].push_back(-1);
          if(temp.size() == 0)
            continue;
          mcols[i][j] = add_or(temp);
        }
      }
     
      std::vector<int> finale;
      for(int i = 0; i <= K; i++) {
        std::vector<int> temp;
        if(i == H)
          break;
        if(K-i >= W)
          continue;
        for(int j = 0; j < spec.size(); j++) {
          if(mrows[j][i%spec[j]] == -1 || mcols[j][(K-i)%spec[j]] == -1) continue;
          temp.push_back(mrows[j][i%spec[j]]);
          temp.push_back(mcols[j][(K-i)%spec[j]]);
        }
     
        finale.push_back(add_and(temp));
      }
      int ans = add_or(finale);
    }

Compilation message (stderr)

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:25:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < spec.size(); i++) {
                      ~~^~~~~~~~~~~~~
vision.cpp:37:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < spec.size(); i++) {
                      ~~^~~~~~~~~~~~~
vision.cpp:50:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < spec.size(); i++) {
                      ~~^~~~~~~~~~~~~
vision.cpp:69:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < spec.size(); i++) {
                      ~~^~~~~~~~~~~~~
vision.cpp:95:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < spec.size(); j++) {
                        ~~^~~~~~~~~~~~~
vision.cpp:103:11: warning: unused variable 'ans' [-Wunused-variable]
       int ans = add_or(finale);
           ^~~

• 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