Submission #960769

#	Time	Username	Problem	Language	Result	Execution time	Memory
960769		steveonalex	Vision Program (IOI19_vision)	C++17	44 / 100	8 ms	2264 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());
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;

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

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

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

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

    void construct_network(int n, int m, int k){
        vector<pair<int, int>> preset;
        for(int i = 0; i <= k; ++i){
            for(int j = -k; j <= k; ++j){
                if (make_pair(i, j) <= make_pair(0, 0)) continue;
                if (abs(i) + abs(j) == k) preset.push_back({i, j});
            }
        }
        #define toIdx(i, j) ((i) * m + (j))

        int memory = n * m;
        for(int i= 0; i<n; ++i) for(int j = 0; j<m; ++j){
            vector<int> jelq;
            for(pair<int, int> t: preset){
                int x = i + t.first, y = j + t.second;
                if (x >= 0 && y >= 0 && x < n && y < m){
                    jelq.push_back(toIdx(x, y));
                }
            }
            if (jelq.empty()) continue;
            add_or(jelq);
            memory++;
            add_and({memory - 1, toIdx(i, j)});
            memory++;
        }
        vector<int> jelq;
        for(int i = n * m + 1; i < memory; i += 2) jelq.push_back(i);
        add_or(jelq);
    }

//     bool solve(int n, int m){
//         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= 10000;
//     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 << rate << "\n";

//     return 0;
// }

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 0 / 15
• Subtask 5: 12 / 12
• Subtask 6: 0 / 8
• Subtask 7: 0 / 14
• Subtask 8: 0 / 19