Submission #171763

#	Time	Username	Problem	Language	Result	Execution time	Memory
171763		AlexLuchianov	Vision Program (IOI19_vision)	C++14	100 / 100	89 ms	9952 KiB

vision

#include "vision.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <fstream>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

std::ifstream in ("log2.txt");

int const nmax = 1000;

struct Point{
  int x;
  int y;
  int id;
} v[1 + nmax * nmax];
std::vector<int> line[1 + nmax * 2], col[1 + nmax * 2];
int answer[1 + nmax];

int lineor[1 + nmax], linexor[1 + nmax];
int color[1 + nmax], colxor[1 + nmax];

int n, m, lim;

int solve(int k){
  std::vector<int> sol;
  for(int i = 0; i < lim; i++){
    std::vector<int> aux_or, aux_xor;
    for(int j = MAX(0, i - k); j <= i; j++){
      aux_or.push_back(lineor[j]);
      aux_xor.push_back(linexor[j]);
    }
    int pos1 = add_or(aux_or);
    int pos2 = add_xor(aux_xor);
    pos2 = add_not(pos2);
    pos1 = add_and({pos1, pos2});
    sol.push_back(pos1);
  }
  int solx = add_or(sol);
  sol.clear();
  for(int i = 0; i < lim; i++){
    std::vector<int> aux_or, aux_xor;
    for(int j = MAX(0, i - k); j <= i; j++){
      aux_or.push_back(color[j]);
      aux_xor.push_back(colxor[j]);
    }
    int pos1 = add_or(aux_or);
    int pos2 = add_xor(aux_xor);
    pos2 = add_not(pos2);
    pos1 = add_and({pos1, pos2});
    sol.push_back(pos1);
  }
  int soly = add_or(sol);
  return add_and({solx, soly});
}

void construct_network(int H, int W, int K) {
  for(int i = 0; i < 94; i++)
    in >> answer[i];

	n = H;
	m = W;
	int ptr = 0;
	lim = n + m - 1;
	for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++){
      v[ptr] = {i + j, i - j + m - 1, ptr};
      line[v[ptr].x].push_back(ptr);
      col[v[ptr].y].push_back(ptr);
      ptr++;
    }

  for(int i = 0; i < lim; i++) {
    lineor[i] = add_or(line[i]);
    linexor[i] = add_xor(line[i]);
  }
  for(int i = 0; i < lim; i++){
    color[i] = add_or(col[i]);
    colxor[i] = add_xor(col[i]);
  }
  int pos1 = solve(K - 1), pos2 = solve(K);
  pos1 = add_not(pos1);
  add_and({pos1, pos2});
}
/*
2 3 3
0 0 0 1
0 0 0 2
0 0 1 0
0 0 1 1
0 0 1 2
0 1 0 2
0 1 1 0
0 1 1 1
0 1 1 2
0 2 1 0
0 2 1 1
0 2 1 2
1 0 1 1
1 0 1 2
1 1 1 2
-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