Submission #413760

#	Time	Username	Problem	Language	Result	Execution time	Memory
413760		ollel	Vision Program (IOI19_vision)	C++17	8 / 100	8 ms	736 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;

// bool add_or(vi& q) {
//   cout << "or:\n";
//   for(auto &i : q) cout << i << " ";cout<<endl;
//   bool ans; cin >> ans;
//   return ans;
// }
//
// bool add_and(vi& q) {
//   cout << "and:\n";
//   for(auto &i : q) cout << i << " ";cout<<endl;
//   bool ans; cin >> ans;
//   return ans;
// }
//
// bool add_not(int x ) {
//   cout << "not:\n";
//   cout << x << endl;
//   bool ans; cin >> ans; return ans;
// }

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_not(x);
  }
}

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;
}
//
// int main() {
//   construct_network(3, 3, 1);
// }

• 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