Submission #198676

#	Time	Username	Problem	Language	Result	Execution time	Memory
198676		Nightlight	Vision Program (IOI19_vision)	C++14	100 / 100	51 ms	4856 KiB

vision

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

typedef pair<int, int> pii;
int R[405], L[405];
int diag[2][405], A[205][205];
int H, W, K, cnt;
int maxk;
vector<int> ask, all;
//diagonal jika 0 menghadap ke kanan, 1 menghadap ke kiri

void compress() {
  vector<int> diag0[H + W], diag1[H + W];
  cnt = 0;
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      diag0[i + j].eb(cnt);
      diag1[(H - i - 1) + j].eb(cnt);
      A[i][j] = cnt++;
    }
  }
/*
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      cout << i + j << " ";
    }
    cout << "\n";
  }
  cout << "\n\n";
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      cout << (H - i - 1) + j << " ";
    }
    cout << "\n";
  }
  cout << "\n\n";
*/
  for(int i = 0; i < maxk; i++) {
    add_or(diag0[i]);
    diag[0][i] = cnt++;
    add_or(diag1[i]);
    diag[1][i] = cnt++;
  }
}

void add() {
  add_or(ask);
  add_xor(ask);
  add_not(cnt + 1);
  add_and({cnt, cnt + 2});
  all.eb(cnt + 3);
  cnt += 4;
}

int check(int len, int id) {
  //sliding window
  ask.clear(), all.clear();
  ask.resize(len);
  int p = 0;
  for(int i = 0; i < len; i++) {
    ask[i] = diag[id][i];
  }
  add();
  for(int i = len; i < maxk; i++) {
    ask[p] = diag[id][i], p = (p + 1) % len;
    add();
  }
  add_or(all), cnt++;
  return cnt - 1;
}

int getlen(int len) {
  R[len] = check(len + 1, 0);
  L[len] = check(len + 1, 1);
  add_and({R[len], L[len]}), cnt++;
  return cnt - 1;
}

void solve() {
  int valK = getlen(K);
  int valK1 = getlen(K - 1);
  add_not(valK1);
  add_and({valK, valK1 + 1});
  int com = cnt + 1;
  cnt += 2;
  //special case
  vector<int> tmp;
  tmp.resize(maxk);
  //right
  for(int i = 0; i < maxk; i++) {
    tmp[i] = diag[0][i];
  }
  add_xor(tmp);
  add_not(L[K - 1]);
  add_and({cnt, cnt + 1, L[K]});
  cnt += 3;
  int right = cnt - 1;
  //left
  for(int i = 0; i < maxk; i++) {
    tmp[i] = diag[1][i];
  }
  add_xor(tmp);
  add_not(R[K - 1]);
  add_and({cnt, cnt + 1, R[K]});
  cnt += 3;
  int left = cnt - 1;
  add_or({com, left, right});
}

void construct_network(int a1, int a2, int a3) {
  H = a1, W = a2, K = a3;
  maxk = H + W - 1;
  compress();
  solve();
}

• 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