oj.uz

Submission #960948

# Submission time Handle Problem Language Result Execution time Memory
960948 2024-04-11T09:45:33 Z steveonalex Vision Program (IOI19_vision) C++17
100 / 100
 13 ms 2068 KB 
#include <bits/stdc++.h>
#include "vision.h"

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)

// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}

ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}

template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T& a, string separator = " ", string finish = "\n"){
        for(auto i: a) cout << i << separator;
        cout << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

// namespace Interactor{
//     vector<bool> a;
//     int m_cnt = 0, o_cnt = 0;

//     void add_not(int x){
//         m_cnt++; o_cnt++;
//         a.push_back(!a[x]);
//     }

//     void add_or(vector<int> x){
//         m_cnt++; o_cnt += x.size();
//         int ans = 0;
//         for(int i: x) ans = ans || a[i];
//         a.push_back(ans);
//     }

//     void add_and(vector<int> x){
//         m_cnt++; o_cnt += x.size();
//         int ans = 1;
//         for(int i: x) ans = ans && a[i];
//         a.push_back(ans);
//     }

//     void add_xor(vector<int> x){
//         m_cnt++; o_cnt += x.size();
//         printArr(x);
//         int ans= 0;
//         for(int i: x) ans = ans ^ a[i];
//         a.push_back(ans);
//     }

    vector<int> get_pref(vector<int> a, int &memory){
        int n = a.size();
        vector<int> pref(n);
        pref[0] = a[0];
        for(int i= 1; i<n; ++i){
            pref[i] = memory++;
            vector<int> cu = {pref[i-1], a[i]};
            add_or(cu);
        }
        return pref;
    }
    vector<int> get_suff(vector<int> a, int &memory){
        int n = a.size();
        vector<int> suff(n);
        suff[n-1] = a[n-1];
        for(int i= n-2; i>=0; --i){
            suff[i] = memory++;
            vector<int> cu = {suff[i+1], a[i]};
            add_or(cu);
        }
        return suff;
    }

    int memory;
    vector<int> dia1, dia2, pref_dia1, pref_dia2, suff_dia1, suff_dia2;
    int check(int n, int m, int k){
        vector<int> d_dia1, d_dia2;
        for(int i = 0; i+k<n+m-1; ++i){
            d_dia1.push_back(memory++);
            d_dia1.push_back(memory++);
            vector<int> cu1 = {dia1[i], suff_dia1[i + k]};
            add_and(cu1);
            vector<int> cu2 = {pref_dia1[i], dia1[i + k]};
            add_and(cu2);
        }
        for(int i = 0; i+k<n+m-1; ++i){
            d_dia2.push_back(memory++);
            d_dia2.push_back(memory++);
            vector<int> cu1 = {dia2[i], suff_dia2[i + k]};
            add_and(cu1);
            vector<int> cu2 = {pref_dia2[i], dia2[i + k]};
            add_and(cu2);
        }

        vector<int> cu = d_dia1;
        for(int i: d_dia2) cu.push_back(i);

        add_or(cu);

        return memory++;
    }
    void construct_network(int n, int m, int k){
        memory = n * m;
        #define toIdx(i, j) ((i) * m + (j))
        // vector<vector<int>> row_cell(n), col_cell(m);
        // for(int i= 0; i<n; ++i) for(int j =0; j<m; ++j){
        //     row_cell[i].push_back(toIdx(i, j));
        //     col_cell[j].push_back(toIdx(i, j));
        // }
        vector<vector<int>> dia1_cell(n + m - 1), dia2_cell(n+m-1);
        for(int i= 0; i<n; ++i) for(int j= 0; j<m; ++j){
            dia1_cell[i+j].push_back(toIdx(i, j));
            dia2_cell[n-i-1+j].push_back(toIdx(i, j));
        }

        // vector<int> row(n), col(m);
        dia1.resize(n+m-1), dia2.resize(n+m-1);
        // for(int i = 0; i<n; ++i) {
        //     add_or(row_cell[i]);
        //     row[i] = memory++;
        // }
        // for(int i = 0; i<m; ++i) {
        //     add_or(col_cell[i]);
        //     col[i] = memory++;
        // }
        for(int i = 0; i<n+m-1; ++i) {
            add_or(dia1_cell[i]);
            dia1[i] = memory++;
        }
        for(int i = 0; i<n+m-1; ++i) {
            add_or(dia2_cell[i]);
            dia2[i] = memory++;
        }

        pref_dia1 = get_pref(dia1, memory), suff_dia1 = get_suff(dia1, memory);
        pref_dia2 = get_pref(dia2, memory), suff_dia2 = get_suff(dia2, memory);


        int x = check(n, m, k);
        if (k == n + m - 2) return;
        int y = check(n, m, k+1);
        add_not(y);
        y = memory++;

        vector<int> cu = {x, y};
        add_and(cu);
    }

//     bool solve(int n, int m){
//         m_cnt = o_cnt = 0;
//         a.clear();
//         a.resize(n * m);
//         vector<pair<int, int>> black;
//         for(int i = 0; i<2; ++i){
//             while(true){
//                 int x = rngesus(0, n*m-1);
//                 if (a[x]) continue;
//                 a[x] = true;
//                 black.push_back({x / m, x % m});
//                 break;
//             }
//         }
//         int k = rngesus(1, n + m - 2);
//         construct_network(n, m, k);
//         return a.back() == (k == abs(black[0].first - black[1].first) + abs(black[0].second - black[1].second));
//     }
// }

// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     int n, m; cin >> n >> m;

//     int t= 100;
//     int rate = 0;
//     for(int iteration = 1; iteration <= t; ++iteration){
//         cout << "Iteration #" << iteration << "\n";
//         bool verdict = Interactor::solve(n, m);
//         if (verdict) cout << "AC" << endl;
//         else cout << "WA" << endl;
//         rate += verdict;

//         cout << Interactor::m_cnt << " " << Interactor::o_cnt << "\n";
//     }
//     cout << rate << "\n";

//     return 0;
// }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 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 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 392 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 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 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 392 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 356 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 344 KB Output is correct
26 Correct 1 ms 344 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 1 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 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 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 392 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 356 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 344 KB Output is correct
26 Correct 1 ms 344 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 348 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 432 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 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 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 392 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 356 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 344 KB Output is correct
26 Correct 1 ms 344 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 348 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 432 KB Output is correct
38 Correct 3 ms 860 KB Output is correct
39 Correct 1 ms 348 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 600 KB Output is correct
43 Correct 3 ms 860 KB Output is correct
44 Correct 3 ms 856 KB Output is correct
45 Correct 3 ms 788 KB Output is correct
46 Correct 3 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 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 2 ms 608 KB Output is correct
6 Correct 2 ms 612 KB Output is correct
7 Correct 1 ms 612 KB Output is correct
8 Correct 1 ms 612 KB Output is correct
9 Correct 2 ms 612 KB Output is correct
10 Correct 2 ms 612 KB Output is correct
11 Correct 2 ms 452 KB Output is correct
12 Correct 2 ms 616 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 2 ms 692 KB Output is correct
17 Correct 2 ms 600 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 436 KB Output is correct
22 Correct 0 ms 348 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 2 ms 604 KB Output is correct
4 Correct 2 ms 656 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 348 KB Output is correct
8 Correct 2 ms 856 KB Output is correct
9 Correct 2 ms 860 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 1 ms 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 6 ms 1236 KB Output is correct
21 Correct 5 ms 1116 KB Output is correct
22 Correct 5 ms 1116 KB Output is correct
23 Correct 4 ms 1116 KB Output is correct
24 Correct 6 ms 1236 KB Output is correct
25 Correct 5 ms 1116 KB Output is correct
26 Correct 5 ms 1116 KB Output is correct
27 Correct 9 ms 2008 KB Output is correct
28 Correct 13 ms 2008 KB Output is correct
29 Correct 9 ms 1884 KB Output is correct
30 Correct 8 ms 1884 KB Output is correct
31 Correct 8 ms 1884 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 344 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2004 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 832 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 6 ms 1376 KB Output is correct
8 Correct 6 ms 1240 KB Output is correct
9 Correct 10 ms 2008 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 440 KB Output is correct

Subtask #8
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 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 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 392 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 356 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 344 KB Output is correct
26 Correct 1 ms 344 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 348 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 432 KB Output is correct
38 Correct 3 ms 860 KB Output is correct
39 Correct 1 ms 348 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 600 KB Output is correct
43 Correct 3 ms 860 KB Output is correct
44 Correct 3 ms 856 KB Output is correct
45 Correct 3 ms 788 KB Output is correct
46 Correct 3 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 1 ms 604 KB Output is correct
50 Correct 1 ms 604 KB Output is correct
51 Correct 1 ms 356 KB Output is correct
52 Correct 2 ms 608 KB Output is correct
53 Correct 2 ms 612 KB Output is correct
54 Correct 1 ms 612 KB Output is correct
55 Correct 1 ms 612 KB Output is correct
56 Correct 2 ms 612 KB Output is correct
57 Correct 2 ms 612 KB Output is correct
58 Correct 2 ms 452 KB Output is correct
59 Correct 2 ms 616 KB Output is correct
60 Correct 1 ms 604 KB Output is correct
61 Correct 1 ms 348 KB Output is correct
62 Correct 2 ms 604 KB Output is correct
63 Correct 2 ms 692 KB Output is correct
64 Correct 2 ms 600 KB Output is correct
65 Correct 1 ms 604 KB Output is correct
66 Correct 1 ms 348 KB Output is correct
67 Correct 1 ms 348 KB Output is correct
68 Correct 1 ms 436 KB Output is correct
69 Correct 0 ms 348 KB Output is correct
70 Correct 0 ms 348 KB Output is correct
71 Correct 0 ms 348 KB Output is correct
72 Correct 2 ms 604 KB Output is correct
73 Correct 2 ms 656 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 348 KB Output is correct
77 Correct 2 ms 856 KB Output is correct
78 Correct 2 ms 860 KB Output is correct
79 Correct 2 ms 604 KB Output is correct
80 Correct 2 ms 604 KB Output is correct
81 Correct 2 ms 604 KB Output is correct
82 Correct 2 ms 604 KB Output is correct
83 Correct 1 ms 600 KB Output is correct
84 Correct 1 ms 604 KB Output is correct
85 Correct 1 ms 344 KB Output is correct
86 Correct 2 ms 604 KB Output is correct
87 Correct 1 ms 604 KB Output is correct
88 Correct 1 ms 348 KB Output is correct
89 Correct 6 ms 1236 KB Output is correct
90 Correct 5 ms 1116 KB Output is correct
91 Correct 5 ms 1116 KB Output is correct
92 Correct 4 ms 1116 KB Output is correct
93 Correct 6 ms 1236 KB Output is correct
94 Correct 5 ms 1116 KB Output is correct
95 Correct 5 ms 1116 KB Output is correct
96 Correct 9 ms 2008 KB Output is correct
97 Correct 13 ms 2008 KB Output is correct
98 Correct 9 ms 1884 KB Output is correct
99 Correct 8 ms 1884 KB Output is correct
100 Correct 8 ms 1884 KB Output is correct
101 Correct 0 ms 348 KB Output is correct
102 Correct 1 ms 344 KB Output is correct
103 Correct 12 ms 2004 KB Output is correct
104 Correct 0 ms 348 KB Output is correct
105 Correct 2 ms 604 KB Output is correct
106 Correct 2 ms 832 KB Output is correct
107 Correct 1 ms 604 KB Output is correct
108 Correct 1 ms 604 KB Output is correct
109 Correct 6 ms 1376 KB Output is correct
110 Correct 6 ms 1240 KB Output is correct
111 Correct 10 ms 2008 KB Output is correct
112 Correct 1 ms 348 KB Output is correct
113 Correct 0 ms 440 KB Output is correct
114 Correct 9 ms 2004 KB Output is correct
115 Correct 2 ms 348 KB Output is correct
116 Correct 2 ms 604 KB Output is correct
117 Correct 4 ms 1276 KB Output is correct
118 Correct 5 ms 1372 KB Output is correct
119 Correct 9 ms 1884 KB Output is correct
120 Correct 8 ms 1884 KB Output is correct
121 Correct 9 ms 1884 KB Output is correct
122 Correct 8 ms 1880 KB Output is correct
123 Correct 9 ms 2008 KB Output is correct
124 Correct 10 ms 2068 KB Output is correct
125 Correct 9 ms 1956 KB Output is correct
126 Correct 9 ms 1880 KB Output is correct
127 Correct 8 ms 1884 KB Output is correct
128 Correct 8 ms 1884 KB Output is correct