Submission #413763

#	Time	Username	Problem	Language	Result	Execution time	Memory
413763		ollel	Vision Program (IOI19_vision)	C++17	8 / 100	6 ms	716 KiB

vision

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

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int w, h, k, n_instructions;


int binary_search() {
  vi p(w*h); rep(i,0,w*h) p[i] = i;

  int psz = p.size();
  while (psz > 1) {
    vi half(psz / 2);
    rep(i,0,psz / 2) half[i] = p[i];
    n_instructions++;
    vi np;
    if (add_or(half)) np = half;
    else {
      rep(i, psz / 2, psz) np.pb(p[i]);
    }
    p = np;
    psz = p.size();
  }
  return p[0];
}

void get_k(int x) {
  int wx = x % w, hx = x / w;
  int first_inst = n_instructions;

  rep(add_w, -k, k + 1) {
    int nw = wx + add_w,
        nh1 = hx + k - abs(add_w),
        nh2 = hx - (k - abs(add_w));

    if (!(0 <= nw && nw < w)) continue;
    if (0 <= nh1 && nh1 < h) {
      int ask = nh1 * w + nw;
      vi k = {ask};
      add_and(k);
      n_instructions++;
    }
    if (0 <= nh2 && nh2 < h) {
      int ask = nh2 * w + nw;
      vi k = {ask};
      add_and(k);
      n_instructions++;
    }
  }

  if (first_inst != n_instructions) {
    vi f;
    rep(i, first_inst, n_instructions) f.pb(i);
    add_or(f);
  }
  else {
    add_or({-1});
  }
}

void construct_network(int H, int W, int K) {
  h = H; w = W; k = K;
  n_instructions = w*h;
  int x = binary_search();
  get_k(x);
  return;
}

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