Submission #403116

#	Time	Username	Problem	Language	Result	Execution time	Memory
403116		rocks03	Vision Program (IOI19_vision)	C++14	66 / 100	133 ms	1824 KiB

vision

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int add_and(vector<int> Ns);
int add_or(vector<int> Ns);
int add_xor(vector<int> Ns);
int add_not(int N);

int H, W, K;

bool valid(int x, int y){
    return (x >= 0 && x < H && y >= 0 && y < W);
}
int dist(int x, int y, int x2, int y2){
    assert(valid(x, y)); assert(valid(x2, y2));
    return abs(x - x2) + abs(y - y2);
}
int cell(int x, int y){
    assert(valid(x, y));
    return x * W + y;
}

void sub6(){
    int cnt = H * W; vector<int> answer;
    vector<int> colonna(W);
    rep(w, 0, W){
        vector<int> v;
        rep(h, 0, H){
            v.pb(cell(h, w));
        }
        add_or(v); colonna[w] = cnt++;
    }
    vector<int> tot;
    rep(w, 0, W) tot.pb(colonna[w]);
    add_xor(tot); int c0 = cnt++;

    vector<int> riga(H);
    rep(h, 0, H){
        vector<int> v;
        rep(w, 0, W){
            v.pb(cell(h, w));
        }
        add_or(v); riga[h] = cnt++;
    }

    tot.clear();
    rep(h, 0, H) tot.pb(riga[h]);
    add_xor(tot); int r0 = cnt++;

    rep(h, 1, H){
        vector<int> v;
        v = {riga[h - 1], riga[h], c0};
        add_and(v); answer.pb(cnt); cnt++;
    }
    rep(w, 1, W){
        vector<int> v;
        v = {colonna[w - 1], colonna[w], r0};
        add_and(v); answer.pb(cnt); cnt++;
    }
    add_or(answer);
}

void construct_network(int H, int W, int K){
    ::H = H, ::W = W, ::K = K;
    if(K == 1){
        sub6();
    } else{
        int cnt = H * W;
        vector<int> v;
        rep(h, 0, H){
            rep(w, 0, W){
                vector<int> v2;
                rep(h2, 0, H){
                    rep(w2, 0, W){
                        if(dist(h, w, h2, w2) == K){
                            v2.pb(cell(h2, w2));
                        }
                    }
                }
                if(!SZ(v2)) continue;
                add_or(v2);
                add_and({cell(h, w), cnt});
                cnt++;
                v.pb(cnt);
                cnt++;
                if(cnt >= 9500){
                    add_or(v); return;
                }
            }
        }
        add_or(v);
    }
}

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