oj.uz

답안 #1075845

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1075845 2024-08-26T09:27:47 Z j_vdd16 Vision Program (IOI19_vision) C++17
0 / 100
 13 ms 2776 KB 
#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;
int rangeOrRow(int l, int r) {
    vi Ns;
    for (int i = l; i < r; i++) {
        Ns.push_back(rows[i]);
    }

    return add_or(Ns);
}

vi 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]);
    }

    //int zero = add_or(rows);

    //cout << "Rowbits: " << endl;
    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());
    }

    //cout << "Colbits: " << endl;
    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({colBits[bit], carry}));
        carry = add_and({colBits[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

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:136:5: note: in expansion of macro 'loop'
  136 |     loop(bit, colBits.size()) {
      |     ^~~~
vision.cpp:144:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     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:150:5: note: in expansion of macro 'loop'
  150 |     loop(bit, sum.size()) {
      |     ^~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Incorrect 2 ms 604 KB on inputs (0, 0), (3, 28), expected 1, but computed 0
5 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 2776 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Incorrect 6 ms 860 KB on inputs (43, 55), (43, 56), expected 1, but computed 0
5 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -