Submission #685229

#	Time	Username	Problem	Language	Result	Execution time	Memory
685229		cadmiumsky	Vision Program (IOI19_vision)	C++14	100 / 100	12 ms	1840 KiB

vision

#include <bits/stdc++.h>
#include "vision.h"

using namespace std;

#define sz(x) (int)(x).size()
//,(x).end()

const int nmax = 200 + 5;
#define less mothioash
int zero;

//int value[] = {1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1};
//int value[] = {1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int value[] = {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1};



int query(int x, int y, int type) {
  vector<int> tmp;
  tmp.emplace_back(x);
  tmp.emplace_back(y);
  if(type == 0)
    return add_and(tmp);
  if(type == 1)
    return add_or(tmp);
  return add_xor(tmp);
}

int less(vector<int> l, int K) {
  //cerr << "Less:\n";
  //for(auto x : l)
    //cerr << value[x] << ' ';
  //cerr << '\n';
  vector<int> pref;
  int last = zero;
  for(int i = 0; i < sz(l); i++) {
    //cerr << value[l[i]] << ' ';
    pref.emplace_back(query(last, l[i], 1));
    last = pref.back();
  }
  //for(auto x : pref)
    //cerr << value[x] << ' ';
  //cerr << '\n';
  vector<int> accum;
  for(int i = K + 1; i < sz(l); i++) {
    accum.emplace_back(query(l[i], pref[i - K - 1], 0));
    //cerr << value[accum.back()] << ' ';
  }
  //cerr << '\n';
  //cerr << '\n';
  
  
  if(sz(accum) == 0) return add_not(zero);
  return add_not(add_or(accum));
}

int equal(vector<int> l, int K) {
  //cerr << "Equal:\n";
  //for(auto x : l)
    //cerr << value[x] << ' ';
  //cerr << '\n';
  vector<int> accum;
  for(int i = K; i < sz(l); i++) {
    accum.emplace_back(query(l[i - K], l[i], 0));
    //cerr << value[accum.back()] << ' ';
  }
  //cerr << '\n';
  if(sz(accum) == 0) return zero;
  return add_or(accum);
}

vector<int> prim[nmax * 2], sec[nmax * 2];

void construct_network(int H, int W, int K) {
  
  vector<int> tmp;
  if(H * W == 2) {
    tmp.emplace_back(0);
    tmp.emplace_back(1);
    add_and(tmp);
    return;
  }
  tmp.emplace_back(0);
  tmp.emplace_back(1);
  tmp.emplace_back(2);
  zero = add_and(tmp);
  
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      int x = i * W + j;
      prim[i + j].emplace_back(x);
      sec[i - j + W - 1].emplace_back(x);
    }
  }
  
  vector<int> p, s;
  for(int i = 0; i < H + W - 1; i++) {
    //cerr << i << '\n';
    //for(auto x : prim[i])
      //cerr << x << '\n';
    //for(auto x : sec[i])
      //cerr << x << '\n';
    //cerr << '\n';
    p.emplace_back(add_xor(prim[i]));
    s.emplace_back(add_xor(sec[i]));
  }
  
  int eq[2] = {equal(p, K), equal(s, K)}, ls[2] = {less(p, K), less(s, K)};
  
  query(query(eq[0], ls[1], 0), query(eq[1], ls[0], 0), 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