Submission #1075871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075871		j_vdd16	Vision Program (IOI19_vision)	C++17	100 / 100	29 ms	3028 KiB

vision

#include "vision.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

typedef uint64_t u64;
typedef int64_t i64;

vi rows, cols;
void construct_network(int H, int W, int K) {
    rows = vi(H);
    loop(i, H) {
        vi Ns;
        loop(j, W) {
            Ns.push_back(i * W + j);
        }

        rows[i] = add_or(Ns);
        //add_log(rows[i]);
    }
    cols = vi(W);
    loop(j, W) {
        vi Ns;
        loop(i, H) {
            Ns.push_back(i * W + j);
        }

        cols[j] = add_or(Ns);
        //add_log(cols[j]);
    }

    vi rowBits;
    loop(bit, 8) {
        vi ands;
        loop(i, H - (1 << bit)) {
            vi rs;
            for (int j = i + (1 << bit); j < H; j += 2 * (1 << bit)) {
                for (int j2 = j; j2 < min(H, j + (1 << bit)); j2++) {
                    rs.push_back(rows[j2]);
                }
            }
            if (rs.size() == 0) {
                break;
            }

            int l = rows[i];
            int r = add_or(rs);

            ands.push_back(add_and({l, r}));
        }

        if (ands.size() == 0) {
            break;
        }
        rowBits.push_back(add_or(ands));
        //add_log(rowBits.back());
    }

    vi colBits;
    loop(bit, 8) {
        vi ands;
        loop(i, W - (1 << bit)) {
            vi rs;
            for (int j = i + (1 << bit); j < W; j += 2 * (1 << bit)) {
                for (int j2 = j; j2 < min(W, j + (1 << bit)); j2++) {
                    rs.push_back(cols[j2]);
                }
            }
            if (rs.size() == 0) {
                break;
            }

            int l = cols[i];
            int r = add_or(rs);

            ands.push_back(add_and({l, r}));
        }

        if (ands.size() == 0) {
            break;
        }
        colBits.push_back(add_or(ands));
        //add_log(colBits.back());
    }

    const int zero = add_not(add_or(rows));
    if (colBits.size() > rowBits.size()) {
        swap(colBits, rowBits);
    }

    vi sum;
    int carry = zero;
    loop(bit, colBits.size()) {
        sum.push_back(add_xor({colBits[bit], rowBits[bit], carry}));
        carry = add_or({
            add_and({colBits[bit], rowBits[bit]}), 
            add_and({colBits[bit], carry}), 
            add_and({carry, rowBits[bit]})
        });
    }
    for (int bit = colBits.size(); bit < rowBits.size(); bit++) {
        sum.push_back(add_xor({rowBits[bit], carry}));
        carry = add_and({rowBits[bit], carry});
    }
    sum.push_back(carry);

    loop(bit, sum.size()) {
        if ((K & (1 << bit)) == 0) {
            sum[bit] = add_not(sum[bit]);
        }
    }

    if (K >= (1 << sum.size())) {
        add_not(add_not(zero));
        return;
    }

    add_and(sum);
}

Compilation message (stderr)

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:19:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define loop(X, N) for(int X = 0; X < (N); X++)
      |                                     ^
vision.cpp:120:5: note: in expansion of macro 'loop'
  120 |     loop(bit, colBits.size()) {
      |     ^~~~
vision.cpp:128:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for (int bit = colBits.size(); bit < rowBits.size(); bit++) {
      |                                    ~~~~^~~~~~~~~~~~~~~~
vision.cpp:19:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define loop(X, N) for(int X = 0; X < (N); X++)
      |                                     ^
vision.cpp:134:5: note: in expansion of macro 'loop'
  134 |     loop(bit, sum.size()) {
      |     ^~~~

• 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