oj.uz

Submission #172962

# Submission time Handle Problem Language Result Execution time Memory
172962 2020-01-02T21:04:26 Z tri Vision Program (IOI19_vision) C++14
59 / 100
 9 ms 1396 KB 
#include <bits/stdc++.h>
#include "vision.h"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = true;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;


int NR, NC;

int lInd(int r, int c) {
    return r * NC + c;
}

int nLoc;
int rOR, cOR;
int preR, sufR, preC, sufC;

int zeroBit;
int oneBit;
int ansBit;

vi sumBits;

void inc(int arg) { // 32 instructions, 64 values read
    assert(sumBits.size() == 16);
    vi newBits;

    int carry = arg;

    for (int i = 0; i < 16; i++) {
        add_xor({sumBits[i], carry});
        newBits.pb(nLoc++);

        add_and({sumBits[i], carry});
        carry = nLoc++;
    }
    sumBits = newBits;
}

void construct_network(int iH, int iW, int K) {
//    ps("started");
    NR = iH, NC = iW;
    // compute prefix tables

    nLoc = NR * NC;

    zeroBit = add_xor({lInd(0, 0), lInd(0, 0)});
    nLoc++;
    oneBit = add_not(zeroBit);
    nLoc++;

    for (int i = 0; i < 16; i++) {
        sumBits.pb(zeroBit);
    }

    rOR = nLoc;
    for (int i = 0; i < NR; i++) {
        vi row;
        for (int j = 0; j < NC; j++) {
            row.pb(lInd(i, j));
        }
        add_or(row);
        nLoc++;
    }

    cOR = nLoc;
    for (int j = 0; j < NC; j++) {
        vi column;
        for (int i = 0; i < NR; i++) {
            column.pb(lInd(i, j));
        }
        add_or(column);
        nLoc++;
    }

    // prefix ORs

    preR = nLoc;
    add_or({rOR});
    nLoc++;
    for (int i = 1; i < NR; i++) {
        add_or({nLoc - 1, rOR + i});
        nLoc++;
    }

    preC = nLoc;
    add_or({cOR});
    nLoc++;
    for (int j = 1; j < NC; j++) {
        add_or({nLoc - 1, cOR + j});
        nLoc++;
    }

    sufR = nLoc;
    add_or({rOR + NR - 1});
    nLoc++;
    for (int i = NR - 2; i >= 0; i--) {
        add_or({nLoc - 1, rOR + i});
        nLoc++;
    }

    sufC = nLoc;
    add_or({cOR + NC - 1});
    nLoc++;
    for (int j = NC - 2; j >= 0; j--) {
        add_or({nLoc - 1, cOR + j});
        nLoc++;
    }

    for (int i = 0; i + 1 < NR; i++) {
        int i1 = preR + i;
        int i2 = sufR + NR - (i + 1) - 1;
        add_and({i1, i2});
        nLoc++;
        inc(nLoc - 1);
    }

    for (int j = 0; j + 1 < NC; j++) {
        int j1 = preC + j;
        int j2 = sufC + NC - (j + 1) - 1;
        add_and({j1, j2});
        nLoc++;
        inc(nLoc - 1);
    }

    ansBit = oneBit;

    for (int i = 0; i < 16; i++) {
        if (K & (1 << i)) {
            ansBit = add_and({ansBit, sumBits[i]});
            nLoc++;
        } else {
            add_not(sumBits[i]);
            nLoc++;

            ansBit = add_and({ansBit, nLoc - 1});
            nLoc++;
        }
    }

    add_or({ansBit});
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 256 KB Output is correct
5 Correct 2 ms 256 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 380 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 256 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 256 KB Output is correct
5 Correct 2 ms 256 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 380 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 1 ms 376 KB Output is correct
24 Correct 3 ms 356 KB Output is correct
25 Correct 3 ms 376 KB Output is correct
26 Correct 3 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 256 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 256 KB Output is correct
5 Correct 2 ms 256 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 380 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 1 ms 376 KB Output is correct
24 Correct 3 ms 356 KB Output is correct
25 Correct 3 ms 376 KB Output is correct
26 Correct 3 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 3 ms 504 KB Output is correct
29 Correct 3 ms 460 KB Output is correct
30 Correct 3 ms 376 KB Output is correct
31 Correct 3 ms 528 KB Output is correct
32 Correct 3 ms 504 KB Output is correct
33 Correct 4 ms 632 KB Output is correct
34 Correct 3 ms 504 KB Output is correct
35 Correct 4 ms 632 KB Output is correct
36 Correct 4 ms 632 KB Output is correct
37 Correct 3 ms 504 KB Output is correct

Subtask #4
15.0 / 15.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
0 / 8.0

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