oj.uz

Submission #890236

# Submission time Handle Problem Language Result Execution time Memory
890236 2023-12-20T18:11:16 Z vjudge1 Vision Program (IOI19_vision) C++17
100 / 100
 9 ms 1656 KB 
#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

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.0 / 10.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 440 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 440 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 436 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 440 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 440 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 436 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 440 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 440 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 440 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 436 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 440 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 3 ms 860 KB Output is correct
39 Correct 1 ms 600 KB Output is correct
40 Correct 1 ms 544 KB Output is correct
41 Correct 2 ms 604 KB Output is correct
42 Correct 2 ms 604 KB Output is correct
43 Correct 3 ms 860 KB Output is correct
44 Correct 3 ms 860 KB Output is correct
45 Correct 3 ms 860 KB Output is correct
46 Correct 4 ms 1124 KB Output is correct
47 Correct 3 ms 860 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 692 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 692 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 600 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 688 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 436 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 436 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 3 ms 828 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 5 ms 1072 KB Output is correct
21 Correct 5 ms 984 KB Output is correct
22 Correct 5 ms 984 KB Output is correct
23 Correct 5 ms 980 KB Output is correct
24 Correct 5 ms 984 KB Output is correct
25 Correct 6 ms 984 KB Output is correct
26 Correct 5 ms 984 KB Output is correct
27 Correct 8 ms 1584 KB Output is correct
28 Correct 8 ms 1496 KB Output is correct
29 Correct 8 ms 1496 KB Output is correct
30 Correct 8 ms 1496 KB Output is correct
31 Correct 8 ms 1496 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1496 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 6 ms 1072 KB Output is correct
8 Correct 5 ms 984 KB Output is correct
9 Correct 8 ms 1460 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #8
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 440 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 440 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 436 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 440 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 3 ms 860 KB Output is correct
39 Correct 1 ms 600 KB Output is correct
40 Correct 1 ms 544 KB Output is correct
41 Correct 2 ms 604 KB Output is correct
42 Correct 2 ms 604 KB Output is correct
43 Correct 3 ms 860 KB Output is correct
44 Correct 3 ms 860 KB Output is correct
45 Correct 3 ms 860 KB Output is correct
46 Correct 4 ms 1124 KB Output is correct
47 Correct 3 ms 860 KB Output is correct
48 Correct 2 ms 604 KB Output is correct
49 Correct 2 ms 604 KB Output is correct
50 Correct 1 ms 604 KB Output is correct
51 Correct 1 ms 600 KB Output is correct
52 Correct 2 ms 604 KB Output is correct
53 Correct 2 ms 692 KB Output is correct
54 Correct 1 ms 604 KB Output is correct
55 Correct 1 ms 604 KB Output is correct
56 Correct 1 ms 604 KB Output is correct
57 Correct 1 ms 692 KB Output is correct
58 Correct 1 ms 604 KB Output is correct
59 Correct 2 ms 600 KB Output is correct
60 Correct 1 ms 600 KB Output is correct
61 Correct 1 ms 604 KB Output is correct
62 Correct 1 ms 604 KB Output is correct
63 Correct 1 ms 604 KB Output is correct
64 Correct 1 ms 604 KB Output is correct
65 Correct 1 ms 688 KB Output is correct
66 Correct 2 ms 604 KB Output is correct
67 Correct 1 ms 604 KB Output is correct
68 Correct 0 ms 348 KB Output is correct
69 Correct 0 ms 436 KB Output is correct
70 Correct 0 ms 348 KB Output is correct
71 Correct 0 ms 348 KB Output is correct
72 Correct 1 ms 604 KB Output is correct
73 Correct 2 ms 600 KB Output is correct
74 Correct 2 ms 604 KB Output is correct
75 Correct 1 ms 604 KB Output is correct
76 Correct 1 ms 436 KB Output is correct
77 Correct 3 ms 604 KB Output is correct
78 Correct 3 ms 604 KB Output is correct
79 Correct 3 ms 604 KB Output is correct
80 Correct 3 ms 604 KB Output is correct
81 Correct 3 ms 828 KB Output is correct
82 Correct 2 ms 860 KB Output is correct
83 Correct 2 ms 604 KB Output is correct
84 Correct 1 ms 604 KB Output is correct
85 Correct 1 ms 604 KB Output is correct
86 Correct 1 ms 604 KB Output is correct
87 Correct 1 ms 604 KB Output is correct
88 Correct 1 ms 604 KB Output is correct
89 Correct 5 ms 1072 KB Output is correct
90 Correct 5 ms 984 KB Output is correct
91 Correct 5 ms 984 KB Output is correct
92 Correct 5 ms 980 KB Output is correct
93 Correct 5 ms 984 KB Output is correct
94 Correct 6 ms 984 KB Output is correct
95 Correct 5 ms 984 KB Output is correct
96 Correct 8 ms 1584 KB Output is correct
97 Correct 8 ms 1496 KB Output is correct
98 Correct 8 ms 1496 KB Output is correct
99 Correct 8 ms 1496 KB Output is correct
100 Correct 8 ms 1496 KB Output is correct
101 Correct 0 ms 348 KB Output is correct
102 Correct 0 ms 348 KB Output is correct
103 Correct 8 ms 1496 KB Output is correct
104 Correct 0 ms 348 KB Output is correct
105 Correct 2 ms 604 KB Output is correct
106 Correct 3 ms 604 KB Output is correct
107 Correct 1 ms 604 KB Output is correct
108 Correct 2 ms 604 KB Output is correct
109 Correct 6 ms 1072 KB Output is correct
110 Correct 5 ms 984 KB Output is correct
111 Correct 8 ms 1460 KB Output is correct
112 Correct 1 ms 344 KB Output is correct
113 Correct 0 ms 348 KB Output is correct
114 Correct 8 ms 1492 KB Output is correct
115 Correct 2 ms 604 KB Output is correct
116 Correct 1 ms 684 KB Output is correct
117 Correct 6 ms 984 KB Output is correct
118 Correct 5 ms 984 KB Output is correct
119 Correct 9 ms 1656 KB Output is correct
120 Correct 9 ms 1496 KB Output is correct
121 Correct 8 ms 1604 KB Output is correct
122 Correct 9 ms 1496 KB Output is correct
123 Correct 9 ms 1496 KB Output is correct
124 Correct 9 ms 1400 KB Output is correct
125 Correct 9 ms 1496 KB Output is correct
126 Correct 8 ms 1496 KB Output is correct
127 Correct 9 ms 1496 KB Output is correct
128 Correct 8 ms 1496 KB Output is correct