Submission #960948

#	Time	Username	Problem	Language	Result	Execution time	Memory
960948		steveonalex	Vision Program (IOI19_vision)	C++17	100 / 100	13 ms	2068 KiB

vision

#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 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 15 / 15
• Subtask 5: 12 / 12
• Subtask 6: 8 / 8
• Subtask 7: 14 / 14
• Subtask 8: 19 / 19