oj.uz

Submission #147952

# Submission time Handle Problem Language Result Execution time Memory
147952 2019-08-31T10:06:57 Z dacin21 Vision Program (IOI19_vision) C++14
59 / 100
 10 ms 1396 KB 
#include "vision.h"

#include <bits/stdc++.h>
using namespace std;



using ll = long long;
using ull = unsigned long long;
using fl = long double;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename S, typename T>
void xmin(S&a, T const&b){if(b<a) a=b;}
template<typename S, typename T>
void xmax(S&a, T const&b){if(b>a) a=b;}

template<bool enabled>
struct Debug{
    template<typename S, typename T = void> struct Tag_Printable : false_type {};
    template<typename S> struct Tag_Printable<S, decltype((void)(cerr << declval<S>()))> : true_type {};
    template<typename S, typename T = void> struct Tag_Iterable: false_type {};
    template<typename S> struct Tag_Iterable<S, decltype((void)(begin(declval<S>()), end(declval<S>())))> : true_type {};
    template<typename T, typename... Args>
    Debug& print(T const&x, true_type, Args...){
        #ifdef LOCAL_RUN
        if(enabled){
            cerr << boolalpha << x;
        }
        #endif // LOCAL_RUN
        return *this;
    }
    template<typename T>
    Debug& print(T const&x, false_type, true_type){
        *this << "[";
        bool first = true;
        for(auto &e:x){
            if(!first) *this << ", ";
            *this << e;
            first = false;
        }
        return *this << "]";
    }
    template<typename S, typename T>
    Debug& print(pair<S, T> const&x, false_type, false_type){
        return *this << "(" << x.first << ", " << x.second << ")";
    }
    template<typename T>
    Debug& operator<<(T const&x){
        return print(x, Tag_Printable<T>{}, Tag_Iterable<T>{});
    }
};
 Debug<true> debug;
// Debug<false> debug; // disable debug printing
#define named(x) string(#x) << " : " <<  x


const int m = __lg(400)+1;

const int ZERO = -1, ONE = -2;

void remove_consts(vector<int> &v){
    v.erase(partition(v.begin(), v.end(), [&](int const&a){return a>=0;}), v.end());
}

int better_and(vector<int> v){
    for(auto const&e:v){
        if(e==ZERO) return ZERO;
    }
    remove_consts(v);
    if(v.empty()) return ONE;
    return add_and(v);
}
int better_or(vector<int> v){
    for(auto const&e:v){
        if(e==ONE) return ONE;
    }
    remove_consts(v);
    if(v.empty()) return ZERO;
    return add_or(v);
}
int better_xor(vector<int> v){
    int flips = 0;
    for(auto const&e:v){
        if(e==ONE) return ++flips;
    }
    remove_consts(v);
    if(v.empty()) return flips ? ONE : ZERO;
    return flips%2 ? add_not(add_xor(v)) : add_xor(v);
}
int better_not(int a){
    return a==ONE ? ZERO : a==ZERO ? ONE : add_not(a);
}
#define add_not better_not
#define add_or better_or
#define add_and better_and
#define add_xor better_xor


int add_majority(int a, int b, int c){
    return add_or({add_and({a, b}), add_and({b, c}), add_and({c, a})});
}
vector<int> build_adder(vector<int> v, vector<int> w){
    assert(v.size() == w.size());
    const int n = v.size();
    vector<int> ret(n);
    ret[0] = add_xor({v[0], w[0]});
    int carry = add_and({v[0], w[0]});
    for(int i=1;i<n;++i){
        ret[i] = add_xor({v[i], w[i], carry});
        carry = add_majority(v[i], w[i], carry);
    }
    //ret[n] = carry;
    return ret;
}

vector<int> build_bits(vector<int> v){
    const int n = v.size();
    vector<int> ret(m, ZERO);
    for(int i=0;i<n;++i){
        int me = v[i];
        // -ret = ~ret+1
        // +1 is done below
        for(auto &e:ret){
            e = add_xor({e, me});
        }
        debug << "mid" << ret << "\n";
        //int no = add_not(me);
        vector<int> tmp(m);
        for(int j=0;j<m;++j){
            tmp[j] = (((i+1)>>j)&1) ? me : ZERO;
        }
        debug << named(tmp) << "\n";
        /*int me = v[i];
        vector<int> tmp(m);
        for(int j=0;j<m;++j){
            tmp[j] = ((i>>j)&1) ? me : ZERO;
        }*/
        ret = build_adder(ret, tmp);
        debug << named(ret) << "\n";
    }
    debug << "Done " << n << "\n";
    return ret;
}

void construct_network(int H, int W, int K) {
    const int X = H, Y = W;
    auto ind = [&](int x, int y){
        assert(0 <= x && x < X);
        assert(0 <= y && y < Y);
        return x*Y+y;
    };
    vector<int> rows(X), cols(Y);
    for(int i=0;i<X;++i){
        vector<int> tmp;
        for(int j=0;j<Y;++j){
            tmp.push_back(ind(i, j));
        }
        rows[i] = add_xor(tmp);
    }
    for(int j=0;j<Y;++j){
        vector<int> tmp;
        for(int i=0;i<X;++i){
            tmp.push_back(ind(i, j));
        }
        cols[j] = add_xor(tmp);
    }
    vector<int> dx = build_bits(rows);
    vector<int> dy = build_bits(cols);
    vector<int> d = build_adder(dx, dy);
    debug << dx << " " << dy << "\n";
    for(int i=0;i<(int)d.size();++i){
        if((~K>>i)&1){
            d[i] = add_not(d[i]);
        }
    }
    debug << named(d) << "\n";
    int ret = add_and(d);
    assert(ret >= 0);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 380 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 2 ms 504 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 3 ms 376 KB Output is correct
25 Correct 3 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 4 ms 504 KB Output is correct
29 Correct 3 ms 504 KB Output is correct
30 Correct 3 ms 376 KB Output is correct
31 Correct 3 ms 504 KB Output is correct
32 Correct 3 ms 504 KB Output is correct
33 Correct 3 ms 504 KB Output is correct
34 Correct 4 ms 632 KB Output is correct
35 Correct 3 ms 504 KB Output is correct
36 Correct 4 ms 608 KB Output is correct
37 Correct 4 ms 632 KB Output is correct
38 Correct 9 ms 1144 KB Output is correct
39 Correct 4 ms 632 KB Output is correct
40 Correct 4 ms 632 KB Output is correct
41 Correct 7 ms 884 KB Output is correct
42 Correct 7 ms 884 KB Output is correct
43 Correct 9 ms 1144 KB Output is correct
44 Correct 10 ms 1144 KB Output is correct
45 Correct 9 ms 1144 KB Output is correct
46 Correct 9 ms 1144 KB Output is correct
47 Correct 9 ms 1144 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1012 KB Output is correct
2 Correct 7 ms 884 KB Output is correct
3 Correct 7 ms 884 KB Output is correct
4 Correct 7 ms 872 KB Output is correct
5 Correct 7 ms 884 KB Output is correct
6 Correct 7 ms 1012 KB Output is correct
7 Correct 7 ms 1012 KB Output is correct
8 Correct 7 ms 1012 KB Output is correct
9 Correct 7 ms 884 KB Output is correct
10 Correct 7 ms 884 KB Output is correct
11 Correct 7 ms 1012 KB Output is correct
12 Correct 7 ms 884 KB Output is correct
13 Correct 7 ms 1012 KB Output is correct
14 Correct 7 ms 884 KB Output is correct
15 Correct 7 ms 888 KB Output is correct
16 Correct 7 ms 884 KB Output is correct
17 Correct 7 ms 884 KB Output is correct
18 Correct 7 ms 884 KB Output is correct
19 Correct 7 ms 884 KB Output is correct
20 Correct 7 ms 1012 KB Output is correct
21 Correct 2 ms 256 KB Output is correct
22 Correct 2 ms 504 KB Output is correct

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 6 ms 760 KB Output is correct
5 Correct 6 ms 760 KB Output is correct
6 Correct 6 ms 732 KB Output is correct
7 Correct 6 ms 760 KB Output is correct
8 Correct 8 ms 1012 KB Output is correct
9 Correct 8 ms 1012 KB Output is correct
10 Correct 8 ms 1012 KB Output is correct
11 Correct 7 ms 1012 KB Output is correct
12 Correct 8 ms 1012 KB Output is correct
13 Correct 7 ms 884 KB Output is correct
14 Correct 7 ms 1012 KB Output is correct
15 Correct 7 ms 884 KB Output is correct
16 Correct 7 ms 984 KB Output is correct
17 Correct 8 ms 884 KB Output is correct
18 Correct 8 ms 1012 KB Output is correct
19 Correct 7 ms 1016 KB Output is correct
20 Incorrect 6 ms 1268 KB WA in grader: Too many instructions
21 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1396 KB WA in grader: Too many instructions
2 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 380 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 2 ms 504 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 3 ms 376 KB Output is correct
25 Correct 3 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 4 ms 504 KB Output is correct
29 Correct 3 ms 504 KB Output is correct
30 Correct 3 ms 376 KB Output is correct
31 Correct 3 ms 504 KB Output is correct
32 Correct 3 ms 504 KB Output is correct
33 Correct 3 ms 504 KB Output is correct
34 Correct 4 ms 632 KB Output is correct
35 Correct 3 ms 504 KB Output is correct
36 Correct 4 ms 608 KB Output is correct
37 Correct 4 ms 632 KB Output is correct
38 Correct 9 ms 1144 KB Output is correct
39 Correct 4 ms 632 KB Output is correct
40 Correct 4 ms 632 KB Output is correct
41 Correct 7 ms 884 KB Output is correct
42 Correct 7 ms 884 KB Output is correct
43 Correct 9 ms 1144 KB Output is correct
44 Correct 10 ms 1144 KB Output is correct
45 Correct 9 ms 1144 KB Output is correct
46 Correct 9 ms 1144 KB Output is correct
47 Correct 9 ms 1144 KB Output is correct
48 Correct 7 ms 1012 KB Output is correct
49 Correct 7 ms 884 KB Output is correct
50 Correct 7 ms 884 KB Output is correct
51 Correct 7 ms 872 KB Output is correct
52 Correct 7 ms 884 KB Output is correct
53 Correct 7 ms 1012 KB Output is correct
54 Correct 7 ms 1012 KB Output is correct
55 Correct 7 ms 1012 KB Output is correct
56 Correct 7 ms 884 KB Output is correct
57 Correct 7 ms 884 KB Output is correct
58 Correct 7 ms 1012 KB Output is correct
59 Correct 7 ms 884 KB Output is correct
60 Correct 7 ms 1012 KB Output is correct
61 Correct 7 ms 884 KB Output is correct
62 Correct 7 ms 888 KB Output is correct
63 Correct 7 ms 884 KB Output is correct
64 Correct 7 ms 884 KB Output is correct
65 Correct 7 ms 884 KB Output is correct
66 Correct 7 ms 884 KB Output is correct
67 Correct 7 ms 1012 KB Output is correct
68 Correct 2 ms 256 KB Output is correct
69 Correct 2 ms 504 KB Output is correct
70 Correct 2 ms 376 KB Output is correct
71 Correct 2 ms 376 KB Output is correct
72 Correct 6 ms 760 KB Output is correct
73 Correct 6 ms 760 KB Output is correct
74 Correct 6 ms 760 KB Output is correct
75 Correct 6 ms 732 KB Output is correct
76 Correct 6 ms 760 KB Output is correct
77 Correct 8 ms 1012 KB Output is correct
78 Correct 8 ms 1012 KB Output is correct
79 Correct 8 ms 1012 KB Output is correct
80 Correct 7 ms 1012 KB Output is correct
81 Correct 8 ms 1012 KB Output is correct
82 Correct 7 ms 884 KB Output is correct
83 Correct 7 ms 1012 KB Output is correct
84 Correct 7 ms 884 KB Output is correct
85 Correct 7 ms 984 KB Output is correct
86 Correct 8 ms 884 KB Output is correct
87 Correct 8 ms 1012 KB Output is correct
88 Correct 7 ms 1016 KB Output is correct
89 Incorrect 6 ms 1268 KB WA in grader: Too many instructions
90 Halted 0 ms 0 KB -