Submission #890236

#	Time	Username	Problem	Language	Result	Execution time	Memory
890236		vjudge1	Vision Program (IOI19_vision)	C++17	100 / 100	9 ms	1656 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

int half_add(int v1, int v2, int &c) {
    c = add_and({v1, v2});
    int re = add_xor({v1, v2});
    return re;
}

int full_add(int v1, int v2, int v3, int &c) {
    int cc, ccc;
    int re1 = half_add(v1, v2, cc);
    int re2 = half_add(re1, v3, ccc);
    c = add_or({cc, ccc});
    return re2;
}

vi add(vi a, vi b, int c0, int c1) {
    int n = max(a.size(), b.size());
    while(a.size() < n) a.push_back(c0);
    while(b.size() < n) b.push_back(c0);
    vi re;
    int carry = c0;
    for(int i = 0; i < n; ++i) {
        re.push_back(full_add(carry, a[i], b[i], carry));
    }
    re.push_back(carry);
    return re;
}

vi calc_dist(vi lin, int c0, int c1) {
    ///va returna adresa catre bitii numarului
    int n = int(lin.size());
    while(n & (n - 1)) lin.push_back(c0), ++n;
    vi re1, re2 = {c0}, re3 = {add_not(add_xor(lin))};

//    cout << "\n\n";
//    for(auto it : lin)
//        cout << it << " ";
//    cout << "\n\n";
    while(n) {
        if(n == 1) {
            break;
        }

        vi ln, imp, par;
        int potential = c1, add = c0;
        for(int i = 0; i < n; i += 2) {
            ln.push_back(add_or(vi{lin[i], lin[i + 1]}));
            int tip01 = add_and({add_not(lin[i]), lin[i + 1]});
            int tip10 = add_and({add_not(lin[i + 1]), lin[i]});
            add = add_or({add, add_and({tip10, potential})});
            potential = add_and({potential, add_not(tip01)});

            par.push_back(lin[i]);
            imp.push_back(lin[i + 1]);
        }

        
        int doua = add_not(add_xor(ln)), samepod = add_xor(ln);
        int v1 = add_or(par), v2 = add_or(imp),
            sametype = add_xor(vi{v1, v2});
        re1.push_back(add_and({sametype, doua}));
        re2.push_back(add_and({add_and({add, doua}), add_not(sametype)}));
        
        lin = ln;
        n /= 2;
    }
//    for(auto it : re1)
//        cout << it << " ";
//    cout << "\n";
//    for(auto it : re2)
//        cout << it << " ";
//    cout << "\n";
//    for(auto it : re3)
//        cout << it << " ";
//    cout << "\n";
    return add(re1, add(re2, re3, c0, c1), c0, c1);
}

void equal(vi a, vi b, int v0, int v1) {
    int n = max(a.size(), b.size());
    while(a.size() < n) a.push_back(v0);
    while(b.size() < n) b.push_back(v0);
    vi dif;
    for(int i = 0; i < n; ++i)
        dif.push_back(add_xor({a[i], b[i]}));
    int re = add_not(add_or(dif));
}
void construct_network(int H, int W, int K) {
    vector<int> lin, col;
    for(int i = 0; i < H; ++i) {
        vi V;
        for(int j = 0; j < W; ++j)
            V.push_back(i * W + j);
        lin.push_back(add_or(V));
    }

    for(int j = 0; j < W; ++j) {
        vi V;
        for(int i = 0; i < H; ++i) {
            V.push_back(i * W + j);
        }
        col.push_back(add_or(V));
    }

    int v0 = -1;
    if(v0 == -1) {
        v0 = add_not({0});
        v0 = add_and(vi{v0, 0});
    }
    int v1 = add_not(v0);
    while((int)lin.size() & ((int)lin.size() - 1)) {
        lin.push_back(v0);
    }

    vi nr1 = calc_dist(lin, v0, v1), nr2 = calc_dist(col, v0, v1);
    vi re = add(nr1, nr2, v0, v1);
    vi repk;
    int k = K;
    while(k) {
        if(k & 1) repk.push_back(v1);
        else repk.push_back(v0);
        k >>= 1;
    }
    equal(repk, re, v0, v1);
}

Compilation message (stderr)

vision.cpp: In function 'vi add(vi, vi, int, int)':
vision.cpp:24:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |     while(a.size() < n) a.push_back(c0);
      |           ~~~~~~~~~^~~
vision.cpp:25:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |     while(b.size() < n) b.push_back(c0);
      |           ~~~~~~~~~^~~
vision.cpp: In function 'vi calc_dist(vi, int, int)':
vision.cpp:64:42: warning: unused variable 'samepod' [-Wunused-variable]
   64 |         int doua = add_not(add_xor(ln)), samepod = add_xor(ln);
      |                                          ^~~~~~~
vision.cpp: In function 'void equal(vi, vi, int, int)':
vision.cpp:87:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |     while(a.size() < n) a.push_back(v0);
      |           ~~~~~~~~~^~~
vision.cpp:88:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   88 |     while(b.size() < n) b.push_back(v0);
      |           ~~~~~~~~~^~~
vision.cpp:92:9: warning: unused variable 're' [-Wunused-variable]
   92 |     int re = add_not(add_or(dif));
      |         ^~

• 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