Submission #418553

#	Time	Username	Problem	Language	Result	Execution time	Memory
418553		wiwiho	Vision Program (IOI19_vision)	C++14	44 / 100	89 ms	7240 KiB

vision

#include "vision.h"

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

int h, w, k;
int getid(int x, int y){
    return x * w + y;
}

void construct_network(int H, int W, int K){
    h = H; w = W; k = K;

    vector<int> large;

    for(int i = 0; i + k + 1 <= h + w - 2; i++){
        vector<int> q1, q2;
        for(int x = 0; x < h; x++){
            for(int y = 0; y < w; y++){
                if(x + y <= i) q1.eb(getid(x, y));
                if(x + y >= i + k + 1) q2.eb(getid(x, y));
            }
        }
//        cerr << "large1 " << i << "\n";
//        printv(q1, cerr);
//        printv(q2, cerr);
        int r1 = add_or(q1), r2 = add_or(q2);
        large.eb(add_and({r1, r2}));
    }

    for(int i = -w + 1; i + k + 1 <= h - 1; i++){
        vector<int> q1, q2;
        for(int x = 0; x < h; x++){
            for(int y = 0; y < w; y++){
                if(x - y <= i) q1.eb(getid(x, y));
                if(x - y >= i + k + 1) q2.eb(getid(x, y));
            }
        }
//        cerr << "large2 " << i << "\n";
//        printv(q1, cerr);
//        printv(q2, cerr);
        int r1 = add_or(q1), r2 = add_or(q2);
        large.eb(add_and({r1, r2}));
    }

    vector<int> small;

    for(int i = 0; i + k <= h + w - 2; i++){
        vector<int> q1, q2;
        for(int x = 0; x < h; x++){
            for(int y = 0; y < w; y++){
                if(x + y == i) q1.eb(getid(x, y));
                if(x + y == i + k) q2.eb(getid(x, y));
            }
        }
//        cerr << "small1 " << i << "\n";
//        printv(q1, cerr);
//        printv(q2, cerr);
        int r1 = add_or(q1), r2 = add_or(q2);
        small.eb(add_and({r1, r2}));
    }

    for(int i = -w + 1; i + k <= h - 1; i++){
        vector<int> q1, q2;
        for(int x = 0; x < h; x++){
            for(int y = 0; y < w; y++){
                if(x - y == i) q1.eb(getid(x, y));
                if(x - y == i + k) q2.eb(getid(x, y));
            }
        }
//        cerr << "small2 " << i << "\n";
//        printv(q1, cerr);
//        printv(q2, cerr);
        int r1 = add_or(q1), r2 = add_or(q2);
        small.eb(add_and({r1, r2}));
    }

    if(large.empty()){
        add_or(small);
        return;
    }

    int rl = add_not(add_or(large)), rs = add_or(small);
    add_and({rl, rs});
}

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