Submission #1019832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019832		ProtonDecay314	Vision Program (IOI19_vision)	C++17	12 / 100	11 ms	2140 KiB

vision

// AM+DG

/*

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
#define L(i, varmn, varmx) for(ll i = varmn; i < varmx; i++)
#define LR(i, varmx, varmn) for(ll i = varmx; i > varmn; i--)
#define LI(i, varmn, varmx) for(int i = varmn; i < varmx; i++)
#define LIR(i, varmx, varmn) for(int i = varmx; i > varmn; i--)
#define pb push_back
#include "vision.h"

int cellnum(int r, int c, int W) {
    return r * W + c;
}

void construct_network(int h, int w, int k) {
    // Falsy/truthy values, may help!
    int falsy = add_xor({0, 0});
    int truthy = add_not(falsy);

    // Row/col stuff
    vi row_has;
    LI(i, 0, h) {
        vi all_in_row;
        LI(j, 0, w) {
            all_in_row.pb(cellnum(i, j, w));
        }
        row_has.pb(add_or(all_in_row));
    }
    vi col_has;
    LI(i, 0, w) {
        vi all_in_col;
        LI(j, 0, h) all_in_col.pb(cellnum(j, i, w));
        col_has.pb(add_or(all_in_col));
    }


    // int row_is_same = add_xor(row_has);
    // int col_is_same = add_xor(col_has);

    // dist_from_orig[i] should OR all points that satisfy x + y = i
    vi dist_from_orig;
    LI(i, 0, h + w - 1) {
        vi all_in_diag;
        LI(x, 0, w) {
            int y = i - x;
            if(y < 0 || y >= h) continue;
            all_in_diag.pb(cellnum(y, x, w));
        }
        assert((int)all_in_diag.size() > 0);
        dist_from_orig.pb(add_or(all_in_diag));
    }

    // dist_from_p2[i] should OR all points that satisfy W - 1 - x + y = i -> y - x = i - W + 1 -> y = x + i - w + 1
    vi dist_from_p2;
    LI(i, 0, h + w - 1) {
        vi all_in_diag;
        LI(x, 0, w) {
            int y = i + x - w + 1;
            if(y < 0 || y >= h) continue;
            all_in_diag.pb(cellnum(y, x, w));
        }
        assert((int)all_in_diag.size() > 0);
        dist_from_p2.pb(add_or(all_in_diag));
    }

    // Next step: determine whether the precondition for necessary condition 1 is true
    // Necessary condition 1: the horizontal and vertical distances must both be no more than k
    
    /// To do this, we can create "sliding windows". Over these sliding windows, we compute the "or" and "xor"
    /// If the "or" is 1 and the "xor" is 0 for any of the sliding windows, we know that the two points are within that sliding window and thus have a separation of no more than k
    int r_is_bounded;
    if(k < h) {
        vi nc1r;
        LI(i, 0, h - k) {
            // In the current window, we will consider the range [i, i + k]
            vi window;
            LI(j, i, i + k + 1) {
                window.pb(row_has[j]);
            }

            int cur_or = add_or(window);
            int cur_xor = add_xor(window);
            int is_contained = add_and({cur_or, add_not(cur_xor)});

            nc1r.pb(is_contained);
        }
        

        r_is_bounded = add_or(nc1r);
    } else {
        r_is_bounded = truthy;
    }

    int c_is_bounded;
    if(k < w) {
        vi nc1c;
        LI(i, 0, w - k) {
            // In the current window, we will consider the range [i, i + k]
            vi window;
            LI(j, i, i + k + 1) {
                window.pb(col_has[j]);
            }

            int cur_or = add_or(window);
            int cur_xor = add_xor(window);
            int is_contained = add_and({cur_or, add_not(cur_xor)});

            nc1c.pb(is_contained);
        }
        c_is_bounded = add_or(nc1c);
    } else {
        c_is_bounded = truthy;
    }


    int oned_is_bounded = add_and({r_is_bounded, c_is_bounded});

    // Next step: determine whether the precondition for necessary condition 2 is true
    // Necessary condition 2: either the top-right diagonal distance is k or the top-left diagonal distance is k
    vi dist_orig_k_sep;

    LI(i, 0, h + w - 1 - k) {
        dist_orig_k_sep.pb(add_and({dist_from_orig[i], dist_from_orig[i + k]}));
    }
    assert((int)dist_orig_k_sep.size() > 0);

    int dist_orig_is_k_sep = add_or(dist_orig_k_sep);

    vi dist_p2_k_sep;

    LI(i, 0, h + w - 1 - k) {
        dist_p2_k_sep.pb(add_and({dist_from_p2[i], dist_from_p2[i + k]}));
    }
    assert((int)dist_p2_k_sep.size() > 0);

    int dist_p2_is_k_sep = add_or(dist_p2_k_sep);

    int dist_diag_is_k_sep = add_or({dist_orig_is_k_sep, dist_p2_is_k_sep});

    // Next step: determine whether both necessary conditions are true. This is the answer
    int yay_yippee_ac_happiness_yooo_nice_slay_yasss_win_bit = add_and({oned_is_bounded, dist_diag_is_k_sep});

    return;
}

Compilation message (stderr)

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:154:9: warning: unused variable 'yay_yippee_ac_happiness_yooo_nice_slay_yasss_win_bit' [-Wunused-variable]
  154 |     int yay_yippee_ac_happiness_yooo_nice_slay_yasss_win_bit = add_and({oned_is_bounded, dist_diag_is_k_sep});
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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