oj.uz

Submission #1067044

# Submission time Handle Problem Language Result Execution time Memory
1067044 2024-08-20T10:04:37 Z jerzyk Vision Program (IOI19_vision) C++17
100 / 100
 9 ms 1948 KB 
#include <bits/stdc++.h>
#include "vision.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
int pos;
int tab[N];
vector<int> c0;

void C0(int n, int m)
{
    vector<int> xd;
    for(int i = 0; i < n * m; ++i) xd.pb(i);
    add_xor(xd);
    c0.pb(n * m);
}

vector<int> S(vector<int> a, vector<int> b)
{
    vector<int> ans;
    ++pos; ans.pb(pos);
    add_xor({a[0], b[0]});
    ++pos;
    add_and({a[0], b[0]});
    for(int i = 1; i < (int)a.size(); ++i)
    {
        int xd = pos;
        ++pos; ans.pb(pos);
        add_xor({xd, a[i], b[i]});
        ++pos; add_and({xd, a[i]});
        ++pos; add_and({xd, b[i]});
        ++pos; add_and({a[i], b[i]});

        ++pos; add_or({pos - 1, pos - 2, pos - 3});
    }
    ans.pb(pos);
    return ans;
}

vector<int> Fix(vector<int> a, int k)
{
    vector<int> ans;
    for(int i = 0; i < (int)a.size(); ++i)
    {
        ++pos; ans.pb(pos);
        if((1<<i)&k)
            add_or({a[i], c0[0]});
        else
            add_not(a[i]);
    }
    return ans;
}

vector<int> Query(int a, int b)
{
    vector<int> ans, x, y;
    if(a == b)
        {ans.pb(a); return ans;}
    x = Query(a, (a + b) / 2);
    y = Query((a + b) / 2 + 1, b);
    return S(x, y);
}

void construct_network(int n, int m, int K)
{
    int p2 = 1, w2 = 0;
    vector<int> s1, s2, sum;
    pos = n * m;
    while(p2 < n || p2 <= m){p2 *= 2; ++w2;}
    C0(n, m);

    int beg = pos + 1;
    for(int i = 1; i <= n; ++i)
    {
        ++pos;
        vector<int> cur;
        for(int j = m * (i - 1); j < m * i; ++j)
            cur.pb(j);
        if(i > 1)
            cur.pb(pos - 1);
        add_xor(cur);
    }
    for(int i = n + 1; i <= p2; ++i)
    {++pos; add_or(c0);}
    //cerr << beg << " " << pos << "\n";
    s1 = Query(beg, pos);

    beg = pos + 1;
    for(int j = 1; j <= m; ++j)
    {
        ++pos;
        vector<int> cur;
        for(int i = j - 1; i < m * n; i += m)
            cur.pb(i);
        if(j > 1)
            cur.pb(pos - 1);
        add_xor(cur);
    }
    for(int j = m + 1; j <= p2; ++j)
        {++pos; add_or(c0);}

    s2 = Query(beg, pos);
    sum = S(s1, s2);

    vector<int> final = Fix(sum, K);
    add_and(final);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 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 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 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 1 ms 348 KB Output is correct
21 Correct 0 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 344 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 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 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 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 1 ms 348 KB Output is correct
21 Correct 0 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 344 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 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 452 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 348 KB Output is correct
34 Correct 1 ms 448 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 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 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 1 ms 348 KB Output is correct
21 Correct 0 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 344 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 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 452 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 348 KB Output is correct
34 Correct 1 ms 448 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 348 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 704 KB Output is correct
46 Correct 2 ms 860 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 2 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 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 736 KB Output is correct
15 Correct 2 ms 856 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 2 ms 856 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 3 ms 860 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 3 ms 604 KB Output is correct
19 Correct 2 ms 600 KB Output is correct
20 Correct 5 ms 1288 KB Output is correct
21 Correct 5 ms 1292 KB Output is correct
22 Correct 5 ms 1292 KB Output is correct
23 Correct 5 ms 1292 KB Output is correct
24 Correct 5 ms 1288 KB Output is correct
25 Correct 5 ms 1288 KB Output is correct
26 Correct 5 ms 1288 KB Output is correct
27 Correct 8 ms 1944 KB Output is correct
28 Correct 8 ms 1740 KB Output is correct
29 Correct 9 ms 1944 KB Output is correct
30 Correct 9 ms 1908 KB Output is correct
31 Correct 8 ms 1940 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 9 ms 1944 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 860 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 5 ms 1292 KB Output is correct
8 Correct 6 ms 1292 KB Output is correct
9 Correct 9 ms 1944 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 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 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 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 1 ms 348 KB Output is correct
21 Correct 0 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 344 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 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 452 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 348 KB Output is correct
34 Correct 1 ms 448 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 348 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 704 KB Output is correct
46 Correct 2 ms 860 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 2 ms 604 KB Output is correct
51 Correct 2 ms 600 KB Output is correct
52 Correct 2 ms 604 KB Output is correct
53 Correct 2 ms 604 KB Output is correct
54 Correct 2 ms 604 KB Output is correct
55 Correct 2 ms 604 KB Output is correct
56 Correct 2 ms 604 KB Output is correct
57 Correct 2 ms 604 KB Output is correct
58 Correct 2 ms 604 KB Output is correct
59 Correct 2 ms 604 KB Output is correct
60 Correct 2 ms 604 KB Output is correct
61 Correct 2 ms 736 KB Output is correct
62 Correct 2 ms 856 KB Output is correct
63 Correct 2 ms 604 KB Output is correct
64 Correct 2 ms 604 KB Output is correct
65 Correct 2 ms 604 KB Output is correct
66 Correct 2 ms 856 KB Output is correct
67 Correct 2 ms 604 KB Output is correct
68 Correct 0 ms 348 KB Output is correct
69 Correct 0 ms 344 KB Output is correct
70 Correct 0 ms 344 KB Output is correct
71 Correct 0 ms 348 KB Output is correct
72 Correct 2 ms 600 KB Output is correct
73 Correct 2 ms 604 KB Output is correct
74 Correct 2 ms 604 KB Output is correct
75 Correct 2 ms 604 KB Output is correct
76 Correct 1 ms 604 KB Output is correct
77 Correct 3 ms 860 KB Output is correct
78 Correct 2 ms 860 KB Output is correct
79 Correct 3 ms 860 KB Output is correct
80 Correct 3 ms 860 KB Output is correct
81 Correct 3 ms 860 KB Output is correct
82 Correct 2 ms 604 KB Output is correct
83 Correct 2 ms 600 KB Output is correct
84 Correct 1 ms 604 KB Output is correct
85 Correct 2 ms 604 KB Output is correct
86 Correct 1 ms 604 KB Output is correct
87 Correct 3 ms 604 KB Output is correct
88 Correct 2 ms 600 KB Output is correct
89 Correct 5 ms 1288 KB Output is correct
90 Correct 5 ms 1292 KB Output is correct
91 Correct 5 ms 1292 KB Output is correct
92 Correct 5 ms 1292 KB Output is correct
93 Correct 5 ms 1288 KB Output is correct
94 Correct 5 ms 1288 KB Output is correct
95 Correct 5 ms 1288 KB Output is correct
96 Correct 8 ms 1944 KB Output is correct
97 Correct 8 ms 1740 KB Output is correct
98 Correct 9 ms 1944 KB Output is correct
99 Correct 9 ms 1908 KB Output is correct
100 Correct 8 ms 1940 KB Output is correct
101 Correct 0 ms 348 KB Output is correct
102 Correct 0 ms 348 KB Output is correct
103 Correct 9 ms 1944 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 860 KB Output is correct
107 Correct 2 ms 604 KB Output is correct
108 Correct 1 ms 604 KB Output is correct
109 Correct 5 ms 1292 KB Output is correct
110 Correct 6 ms 1292 KB Output is correct
111 Correct 9 ms 1944 KB Output is correct
112 Correct 1 ms 344 KB Output is correct
113 Correct 1 ms 344 KB Output is correct
114 Correct 9 ms 1944 KB Output is correct
115 Correct 2 ms 600 KB Output is correct
116 Correct 2 ms 604 KB Output is correct
117 Correct 5 ms 1292 KB Output is correct
118 Correct 5 ms 1292 KB Output is correct
119 Correct 9 ms 1948 KB Output is correct
120 Correct 8 ms 1788 KB Output is correct
121 Correct 8 ms 1692 KB Output is correct
122 Correct 8 ms 1724 KB Output is correct
123 Correct 9 ms 1944 KB Output is correct
124 Correct 8 ms 1944 KB Output is correct
125 Correct 8 ms 1940 KB Output is correct
126 Correct 8 ms 1688 KB Output is correct
127 Correct 8 ms 1944 KB Output is correct
128 Correct 9 ms 1936 KB Output is correct