oj.uz

답안 #1019832

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1019832 2024-07-11T09:27:18 Z ProtonDecay314 Vision Program (IOI19_vision) C++17
12 / 100
 11 ms 2140 KB 
// 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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 432 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB on inputs (0, 0), (0, 1), expected 1, but computed 0
6 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 432 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB on inputs (0, 0), (0, 1), expected 1, but computed 0
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 432 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB on inputs (0, 0), (0, 1), expected 1, but computed 0
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 432 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB on inputs (0, 0), (0, 1), expected 1, but computed 0
6 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 676 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 432 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 436 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 436 KB Output is correct
17 Correct 2 ms 600 KB Output is correct
18 Correct 2 ms 856 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #6
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB on inputs (0, 0), (0, 1), expected 1, but computed 0
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 2140 KB on inputs (80, 199), (81, 199), expected 1, but computed 0
2 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 432 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB on inputs (0, 0), (0, 1), expected 1, but computed 0
6 Halted 0 ms 0 KB -