제출 #658936

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
658936		jiahng	Vision Program (IOI19_vision)	C++14	26 / 100	18 ms	3024 KiB

vision

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

typedef long long ll;
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 201
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;

int H,W;
bool valid(int x,int y){
    return (x >= 0 && x < H && y >= 0 && y < W);
}
int ordiag1[maxn][maxn],ordiag2[maxn][maxn],xordiag1[maxn][maxn],xordiag2[maxn][maxn];
void construct_network(int H, int W, int K) {
    vi ans;
    ::H = H; ::W = W;
    // precomp OR and XOR in each diagonal
    for (int si=0,sj=W-1;si<H;(sj==0?si++:sj--)){
        vi v;
        for (int i=si,j=sj;valid(i,j);i++,j++) v.pb(i*W+j);
        ordiag1[si][sj] = add_or(v);
        xordiag1[si][sj] = add_xor(v);
    }

    for (int si=0,sj=0;si<H;(sj==W-1?si++:sj++)){ // antidiagonal
        vi v;
        for (int i=si,j=sj;valid(i,j);i++,j--) v.pb(i*W+j);
        ordiag2[si][sj] = add_or(v);
        xordiag2[si][sj] = add_xor(v);
    }

    vi axis1_unstrict_or, axis2_strict_or;
    for (int si=0,sj=W-1;si<H;(sj==0?si++:sj--)){
        vi orv,xorv;
        for (int k=0;k<=K;k++){
            int diagi = si+k, diagj = sj;
            diagi -= diagj; diagj = 0;

            if (!valid(diagi, diagj)){
                diagj -= diagi; diagi = 0;
            }
            if (!valid(diagi, diagj)) continue;
            assert(diagi == 0 || diagj == 0);
            orv.pb(ordiag1[diagi][diagj]);
            xorv.pb(xordiag1[diagi][diagj]);
        }
        if (orv.empty()) continue;
        axis1_unstrict_or.pb(add_and({add_or(orv), add_not(add_xor(xorv))}));
    }
    int distleqK1 = add_or(axis1_unstrict_or);
    for (int si=0,sj=0;si<H;(sj==W-1?si++:sj++)){
        int diagi = si+K, diagj = sj;
        diagj += diagi; diagi = 0;
        if (!valid(diagi, diagj)){
            diagi -= (-diagj + W - 1);
            diagj = W-1; 
        }
        if (!valid(diagi, diagj)) continue;
        int or_idx = add_or({ordiag2[diagi][diagj], ordiag2[si][sj]});
        int xor_idx = add_xor({xordiag2[diagi][diagj], xordiag2[si][sj]});
        axis2_strict_or.pb(add_and({or_idx, add_not(xor_idx)})); // Whether it is distance K on the axis
    }
    int distK2 = add_or(axis2_strict_or);
    int ok1 = add_and({distleqK1, distK2});

    vi axis2_unstrict_or, axis1_strict_or;

    for (int si=0,sj=0;si<H;(sj==W-1?si++:sj++)){ // antidiagonal
        vi orv,xorv;
        for (int k=0;k<=K;k++){
            int diagi = si+k, diagj = sj;
            diagj += diagi; diagi = 0;
            if (!valid(diagi, diagj)){
                diagi -= (-diagj + W - 1);
                diagj = W-1;
            }
            if (!valid(diagi, diagj)) continue;

            orv.pb(ordiag2[diagi][diagj]);
            xorv.pb(xordiag2[diagi][diagj]);
        }
        axis2_unstrict_or.pb(add_and({add_or(orv), add_not(add_xor(xorv))}));
    }
    int distleqK2 = add_or(axis2_unstrict_or);

    for (int si=0,sj=W-1;si<H;(sj==0?si++:sj--)){ // diagonal
        int diagi = si+K, diagj = sj;
        diagj -= diagi; diagi = 0;
        if (!valid(diagi, diagj)){
            diagi -= diagj;
            diagj = 0;
        }
        if (!valid(diagi, diagj)) continue;
        int or_idx = add_or({ordiag1[diagi][diagj], ordiag1[si][sj]});
        int xor_idx = add_xor({xordiag1[diagi][diagj], xordiag1[si][sj]});
        axis1_strict_or.pb(add_and({or_idx, add_not(xor_idx)})); // Whether it is distance K on the axis
    }
    int distK1 = add_or(axis1_strict_or);
    int ok2 = add_and({distleqK2, distK1});
    
    add_or({ok1, ok2});
}

• 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: 14 / 14
• Subtask 8: 0 / 19