oj.uz

Submission #778472

# Submission time Handle Problem Language Result Execution time Memory
778472 2023-07-10T10:53:44 Z kamelfanger83 Vision Program (IOI19_vision) C++14
32 / 100
 7 ms 1236 KB 
#include "vision.h"
#include <cassert>

using namespace std;

int log2(int n){
    int res = 0, tres = 1;
    while(tres < n){
        tres <<= 1;
        res++;
    }
    return res;
}

void construct_network(int H, int W, int K) {
    if (H * W == 2) {
        add_and({0, 1});
        return;
    }
    int log2H = log2(H);
    int log2W = log2(W);
    int z = add_and({0,1,2});
    int o = add_not(z);
    vector<int> rows;
    for (int x = 0; x < H; ++x) {
        vector<int> tr;
        for (int y = 0; y < W; ++y) {
            tr.push_back(x * W + y);
        }
        rows.push_back(add_xor(tr));
    }
    vector<int> cols;
    for (int y = 0; y < W; ++y) {
        vector<int> tc;
        for (int x = 0; x < H; ++x) {
            tc.push_back(x * W + y);
        }
        cols.push_back(add_xor(tc));
    }
    vector<int> Hind;
    for (int divs = 0; divs < log2H; divs++) {
        vector<int> tN;
        for (int x = 0; x < H; ++x) {
            if ((x >> divs) & 1) tN.push_back(rows[x]);
        }
        int raw = add_xor(tN);
        int nadj = o;
        if (divs != 0 && 1 << divs < H){
            vector<int> boths;
            for (int cen = 1 << divs; cen < H; cen += 1 << divs) {
                vector<int> pre;
                for (int x = cen - (1 << (divs - 1)); x < cen; ++x) {
                    pre.push_back(rows[x]);
                }
                int inpre = add_xor(pre);
                vector<int> post;
                for (int x = cen; x < cen + (1 << (divs - 1)) && x < H; ++x) {
                    post.push_back(rows[x]);
                }
                int inpost = add_xor(post);
                boths.push_back(add_and({inpre, inpost}));
            }
            int adj = add_or(boths);
            nadj = add_not(adj);
        }
        Hind.push_back(add_and({raw, nadj}));
    }
    for (int i = 0; i < log2W - log2H; ++i) {
        Hind.push_back(add_and({z}));
    }
    vector<int> Wind;
    for (int divs = 0; divs < log2W; divs++) {
        vector<int> tN;
        for (int y = 0; y < W; ++y) {
            if ((y >> divs) & 1) tN.push_back(cols[y]);
        }
        int raw = add_xor(tN);
        int nadj = o;
        if (divs != 0 && 1 << divs < W){
            vector<int> boths;
            for (int cen = 1 << divs; cen < W; cen += 1 << divs) {
                vector<int> pre;
                for (int y = cen - (1 << (divs - 1)); y < cen; ++y) {
                    pre.push_back(cols[y]);
                }
                int inpre = add_xor(pre);
                vector<int> post;
                for (int y = cen; y < cen + (1 << (divs - 1)) && y < W; ++y) {
                    post.push_back(cols[y]);
                }
                int inpost = add_xor(post);
                boths.push_back(add_and({inpre, inpost}));
            }
            int adj = add_or(boths);
            nadj = add_not(adj);
        }
        Wind.push_back(add_and({raw, nadj}));
    }
    for (int i = 0; i < log2H - log2W; ++i) {
        Wind.push_back(add_and({z}));
    }

    assert(Hind.size() == Wind.size());

    int addbits = max(log2H, log2W);
    vector<int> addeds, carries;
    addeds.push_back(add_xor({Wind[0], Hind[0]}));
    carries.push_back(add_and({Wind[0], Hind[0]}));
    for (int i = 1; i < addbits; ++i) {
        addeds.push_back(add_xor({Wind[i], Hind[i], carries[i - 1]}));
        int o1 = add_and({Wind[i], Hind[i]});
        int o2 = add_and({carries[i - 1], Hind[i]});
        int o3 = add_and({Wind[i], carries[i - 1]});
        carries.push_back(add_or({o1, o2, o3}));
    }
    addeds.push_back(add_and({carries.back()}));
    vector<int> Kbits;
    for (int i = 0; i < addeds.size(); ++i) {
        if (K & 1) Kbits.push_back(add_and({o}));
        else Kbits.push_back(add_and({z}));
        K >>=1;
    }
    assert(K == 0);
    vector<int> XORS;
    for (int i = 0; i < addeds.size(); ++i) {
        XORS.push_back(add_xor({addeds[i], Kbits[i]}));
    }
    vector<int> NOTS;
    for (int i = 0; i < XORS.size(); ++i) {
        NOTS.push_back(add_not(XORS[i]));
    }
    add_and(NOTS);
}

Compilation message

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:118:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for (int i = 0; i < addeds.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~
vision.cpp:125:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for (int i = 0; i < addeds.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~
vision.cpp:129:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for (int i = 0; i < XORS.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 4 ms 268 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 4 ms 268 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Incorrect 0 ms 212 KB on inputs (0, 1), (0, 4), expected 1, but computed 0
20 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 4 ms 268 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Incorrect 0 ms 212 KB on inputs (0, 1), (0, 4), expected 1, but computed 0
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 4 ms 268 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Incorrect 0 ms 212 KB on inputs (0, 1), (0, 4), expected 1, but computed 0
20 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB on inputs (0, 3), (0, 96), expected 0, but computed 1
3 Halted 0 ms 0 KB -

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 4 ms 724 KB Output is correct
21 Correct 4 ms 724 KB Output is correct
22 Correct 4 ms 692 KB Output is correct
23 Correct 4 ms 712 KB Output is correct
24 Correct 4 ms 724 KB Output is correct
25 Correct 4 ms 724 KB Output is correct
26 Correct 4 ms 724 KB Output is correct
27 Correct 7 ms 1108 KB Output is correct
28 Correct 7 ms 1108 KB Output is correct
29 Correct 7 ms 1108 KB Output is correct
30 Correct 7 ms 1236 KB Output is correct
31 Correct 6 ms 1108 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1192 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 7 ms 1108 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 4 ms 268 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Incorrect 0 ms 212 KB on inputs (0, 1), (0, 4), expected 1, but computed 0
20 Halted 0 ms 0 KB -