Submission #1020778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020778		c2zi6	Vision Program (IOI19_vision)	C++14	100 / 100	38 ms	6200 KiB

vision

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "vision.h"

void construct_network(int H, int W, int K) {
    VVI left, right;
    int dsize = H+W-1;
    left = right = VVI(dsize);
    rep(i, H) rep(j, W) {
        left[j-i+H-1].pb(i*W + j);
        right[i+j].pb(i*W + j);
    }
    int start = H*W;
    auto addgate1 = [&](VVI side) {
        int d[4];
        // d[0] or 
        // d[1] xor
        // d[2] not xor
        // d[3] (not xor) and (or)
        d[0] = start;
        d[1] = d[0] + dsize;
        d[2] = d[1] + dsize;
        d[3] = d[2] + dsize;
        rep(i, dsize) {
            add_or(side[i]);
        }
        rep(i, dsize) {
            add_xor(side[i]);
        }
        rep(i, dsize) {
            add_not(d[1] + i);
        }
        rep(i, dsize) {
            add_and({d[2]+i, d[0]+i});
        }
        start = d[3] + dsize;
        return PII{d[0], d[3]};
    };
    auto addgate2 = [&](int L, int dor) {
        int groupsize = dsize-L+1;
        int group[4];
        // group[0] or 
        // group[1] xor
        // group[2] not xor
        // group[3] (not xor) and (or)
        group[0] = start;
        group[1] = group[0] + groupsize;
        group[2] = group[1] + groupsize;
        group[3] = group[2] + groupsize;
        rep(i, groupsize) {
            VI tmp;
            replr(j, i, i+L-1) tmp.pb(dor+j);
            add_or(tmp);
        }
        rep(i, groupsize) {
            VI tmp;
            replr(j, i, i+L-1) tmp.pb(dor+j);
            add_xor(tmp);
        }
        rep(i, groupsize) {
            add_not(group[1] + i);
        }
        rep(i, groupsize) {
            add_and({group[0] + i, group[2] + i});
        }
        start = group[3] + groupsize;
        return group[3];
    };
    auto[d1or, d1both] = addgate1(left);
    auto[d2or, d2both] = addgate1(right);
    auto addgate3 = [&](int L) {
        int d1group = addgate2(L, d1or);
        int d2group = addgate2(L, d2or);
        VI tmp;
        tmp = VI();
        replr(i, d1both, d1both + dsize-1) tmp.pb(i);
        replr(i, d1group, d1group + (dsize-L+1) - 1) tmp.pb(i);
        add_or(tmp);
        start++;
        tmp = VI();
        replr(i, d2both, d2both + dsize-1) tmp.pb(i);
        replr(i, d2group, d2group + (dsize-L+1) - 1) tmp.pb(i);
        add_or(tmp);
        start++;
        add_and({start-1, start-2});
        return start++;
    };
    int g1 = addgate3(K+1); // must be true
    int g2 = addgate3(K); // must be false
    int g2not = add_not(g2);
    add_and({g1, g2not});
}

/*
 * add_not
 * add_and
 * add_or
 * add_xor
*/

Compilation message (stderr)

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:98:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |     auto[d1or, d1both] = addgate1(left);
      |         ^
vision.cpp:99:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |     auto[d2or, d2both] = addgate1(right);
      |         ^

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