Submission #581216

#	Time	Username	Problem	Language	Result	Execution time	Memory
581216		drdilyor	Vision Program (IOI19_vision)	C++17	100 / 100	18 ms	2096 KiB

vision

#if defined(ONPC) && !defined(_GLIBCXX_ASSERTIONS)
    #define _GLIBCXX_ASSERTIONS
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#ifdef ONPC
    #define cerr cout
    #include "t_debug.cpp"
#else
    #define debug(...) 42
#endif
#define allit(a) (a).begin(), (a).end()
#define sz(a) ((int) (a).size())
#include "vision.h"

using namespace std;
using ll = long long;
using vi = vector<int>;
namespace pd = __gnu_pbds;
template<typename K>
using ordered_set = pd::tree<K, pd::null_type, less<int>, pd::rb_tree_tag, pd::tree_order_statistics_node_update>;
template<typename... T>
using gp_hash_table = pd::gp_hash_table<T...>;//simple using statement gives warnings

const int INF = 1e9;
const ll INFL = 1e18;
const int N = 1e5;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(RANDOM);

#define ENC(i,j) ((i) * m + (j))
void construct_network(int n, int m, int dist) {

    vi diag1(n+m), diag2(n+m);

    for (int i = 0; i < n + m; i++) {
        vi pos;
        for (int j = 0; j <= i; j++) {
            int row = j, col = i - j;
            if (0 <= row && row < n && 0 <= col && col < m) {
                pos.push_back(ENC(row, col));
            }
        }
        diag1[i] = pos.empty() ? -1 : add_or(pos);
    }
    for (int d = 0; d < n+m; d++) {
        vi pos;
        for (int i = 0, j = d - n; i < n && j < m; i++, j++) {
            if (j >= 0) {
                pos.push_back(ENC(i, j));
            }
        }
        diag2[d] = pos.empty() ? -1 : add_or(pos);
    }


    vi eq, gt;
    for (int i = 0; i + dist < sz(diag1); i++) {
        if (diag1[i] != -1 && diag1[i+dist] != -1) {
            eq.push_back(add_and({diag1[i], diag1[i+dist]}));
        }
        if (diag2[i] != -1 && diag2[i+dist] != -1) {
            eq.push_back(add_and({diag2[i], diag2[i+dist]}));
        }
    }
    for (int i = 0; i < sz(diag1); i++) {
        vi cur1, cur2;
        for (int j = i + dist + 2; j < sz(diag1); j += 2) {
            if (diag1[i] != -1 && diag1[j] != -1)
                cur1.push_back(diag1[j]);
            if (diag2[i] != -1 && diag2[j] != -1)
                cur2.push_back(diag2[j]);
        }
        if (!cur1.empty()) gt.push_back(add_and({diag1[i], add_or(cur1)}));
        if (!cur2.empty()) gt.push_back(add_and({diag2[i], add_or(cur2)}));
    }
    if (!gt.empty()) 
        add_and({add_or(eq), add_not(add_or(gt))});
    else
        add_or(eq);

    return;
}
#undef ENC

• 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