Submission #600307

#	Time	Username	Problem	Language	Result	Execution time	Memory
600307		Sam_a17	Vision Program (IOI19_vision)	C++14	100 / 100	246 ms	10936 KiB

vision

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

#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(x) cerr << #x << " " << x << endl;

#define pb push_back
#define ld long double
#define ll long long

int add_and(std::vector<int> Ns);
int add_or(std::vector<int> Ns);
int add_xor(std::vector<int> Ns);
int add_not(int N);

void pr(vector<int>& a) {
  cerr << "[ ";
  for(auto i: a) {
    cerr << i << " ";
  }
  cerr << "]" << endl;
}

void pr(deque<int>& a) {
  cerr << "[ ";
  for(auto i: a) {
    cerr << i << " ";
  }
  cerr << "]" << endl;
}

const int N = 205, M = 1e5 + 10;
int a[N][N];

int lxor[M], rxor[M];
int lor[M], ror[M];

vector<int> rows[M], cols[M];

void construct_network(int H, int W, int K) {
  
  int cnt = H * W, qn = 0;
  int n = H, m = W;

  vector<pair<int, int>> diag;


  //
  for(int i = m - 1; i >= 0; i--) {
    int x = 0, y = i;
    while(x < H && y < W) {
      rows[qn].push_back(x * W + y);
      x++, y++;
    }

    add_or(rows[qn]);
    add_xor(rows[qn]); 
    
    ror[qn] = cnt;
    rxor[qn] = cnt + 1;
    
    cnt += 2;
    qn++;
  }
  
  //
  for(int i = 1; i < n; i++) {
    int x = i, y = 0;
    while(x < H && y < W) {
      rows[qn].push_back(x * W + y);
      x++, y++;
    }

    add_or(rows[qn]);
    add_xor(rows[qn]); 
    
    ror[qn] = cnt;
    rxor[qn] = cnt + 1;
    
    cnt += 2;
    qn++;
  }

  dbg(qn)
  //
  qn = 0;
  for(int i = 0; i < m; i++) {
    int x = 0, y = i;
    while(x < n && y >= 0) {
      cols[qn].push_back(x * W + y);
      x++, y--;
    }

    add_or(cols[qn]);
    add_xor(cols[qn]); 
    
    lor[qn] = cnt;
    lxor[qn] = cnt + 1;
    
    cnt += 2;
    qn++;
  }
  
  //
  for(int i = 1; i < n; i++) {
    int x = i, y = m - 1;
    while(x < n && y >= 0) {
      cols[qn].push_back(x * W + y);
      x++, y--;
    }

    add_or(cols[qn]);
    add_xor(cols[qn]); 
    
    lor[qn] = cnt;
    lxor[qn] = cnt + 1;

    cnt += 2;
    qn++;
  }
  dbg(qn)


  auto slidingWindow = [&](int ki)->int {
    vector<int> answ1, answ2;
    for(int i = 0; i + ki < n + m - 1; i++) {
      vector<int> askii, askii2;  
      for(int j = i; j <= i + ki; j++) {
        askii.push_back(ror[j]);
        askii2.push_back(rxor[j]);
      }

      pr(askii);

      add_or(askii);
      add_xor(askii2);
      add_xor({cnt, cnt + 1});
      answ1.push_back(cnt + 2);
      cnt += 3;


      askii.clear(), askii2.clear();
      for(int j = i; j <= i + ki; j++) {
        askii.push_back(lor[j]);
        askii2.push_back(lxor[j]);
      }

      add_or(askii);
      add_xor(askii2);
      add_xor({cnt, cnt + 1});
      answ2.push_back(cnt + 2);
      cnt += 3;
    }

    add_or(answ1);
    cnt++;
    
    add_or(answ2);
    cnt++;

    add_and({cnt - 1, cnt - 2});
    cnt++;
    return cnt - 1;
  };
  
  
  if(K == 1) {
    int s1 = slidingWindow(1);
    int s2 = slidingWindow(1);
    add_and({s1, s2});
  } else {
    add_xor({slidingWindow(K - 1), slidingWindow(K)});
  }

}

• 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