Submission #284070

#	Time	Username	Problem	Language	Result	Execution time	Memory
284070		kartel	Vision Program (IOI19_vision)	C++14	100 / 100	106 ms	9404 KiB

vision

#include <bits/stdc++.h>
//#include "grader.cpp"
#include "vision.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("no-stack-protector")
#define F first
#define S second
#define pb push_back
#define N 205
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e9)
#define el '\n'
#define Max_A int(1e9)
//#define el endl
#define pii pair <int, int>
#define piii pair <int, pair <int, int> >
#define psi pair <string, int>
#define err ld(1e-9)
#define Max_S int(3e6)
#define last(x) (x).back()
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;

int i, j;
int diag_r[2][N][N];
int diag_l[2][N][N];
int diag_R[N * N][2];
int diag_L[N * N][2];

void construct_network(int n, int m, int k)
{
    vi vc;
    int num = n * m;
    for (i = 0; i < n; i++)
      {
          int x = i;

          if (i == m)
            break;

          vc.pb(x * m + x);
      }

    add_or(vc);
//    cerr << num << el;

    diag_r[0][0][0] = num++;
    diag_R[n - 1][0] = num - 1;

    for (i = 1; i < n; i++)
    {
        int x = i;
        int y = 0;

        vi vc;
        vc.clear();

        for (; x < n && y < m; x++, y++)
            vc.pb(x * m + y);

        add_or(vc);

//        cerr << num << el;

        diag_r[0][i][0] = num++;
        diag_R[n - i - 1][0] = num - 1;
    }

    for (j = 1; j < m; j++)
    {
        int x = 0;
        int y = j;

        vi vc;
        vc.clear();

        for (; x < n && y < m; x++, y++)
            vc.pb(x * m + y);

        add_or(vc);
//        cerr << num << el;

        diag_r[0][0][j] = num++;
        diag_R[n + j - 1][0] = num - 1;
    }

    //------------------

//    cout << el;

    int y = m - 1;
    vc.clear();

    for (i = 0; i < n && y >= 0; i++)
      {
          int x = i;

          vc.pb(x * m + y);
          y--;
      }

    add_or(vc);
//    cerr << num << el;

    diag_l[0][0][m - 1] = num++;
    diag_L[n - 1][0] = num - 1;

    for (i = 1; i < n; i++)
    {
        int x = i;
        int y = m - 1;

        vi vc;
        vc.clear();

        for (; x < n && y >= 0; x++, y--)
            vc.pb(x * m + y);

        add_or(vc);
//        cerr << num << el;

        diag_l[0][i][m - 1] = num++;
        diag_L[n - i - 1][0] = num - 1;
    }

    for (j = 0; j < m - 1; j++)
    {
        int x = 0;
        int y = j;

        vi vc;
        vc.clear();

        for (; x < n && y >= 0; x++, y--)
            vc.pb(x * m + y);

        add_or(vc);
//        cerr << num << el;

        diag_l[0][0][j] = num++;
        diag_L[n + m - j - 2][0] = num - 1;
    }

    //-----------------------------------
//    cout << el;
    vc.clear();

    for (i = 0; i < n; i++)
      {
          int x = i;

          if (i == m)
            break;

          vc.pb(x * m + x);
      }
    vc.pb(diag_r[0][0][0]);

    add_xor(vc);
//    cerr << num << el;

    diag_r[1][0][0] = num++;
    diag_R[n - 1][1] = num - 1;

    for (i = 1; i < n; i++)
    {
        int x = i;
        int y = 0;

        vi vc;
        vc.clear();

        for (; x < n && y < m; x++, y++)
            vc.pb(x * m + y);

        vc.pb(diag_r[0][i][0]);

        add_xor(vc);
//        cerr << num << el;

        diag_r[1][i][0] = num++;
        diag_R[n - i - 1][1] = num - 1;
    }

    for (j = 1; j < m; j++)
    {
        int x = 0;
        int y = j;

        vi vc;
        vc.clear();

        for (; x < n && y < m; x++, y++)
            vc.pb(x * m + y);

        vc.pb(diag_r[0][0][j]);

        add_xor(vc);
//        cerr << num << el;

        diag_r[1][0][j] = num++;
        diag_R[n + j - 1][1] = num - 1;
    }

    //--------------------------------
    vc.clear();

//    cout << el;

    y = m - 1;

    for (i = 0; i < n && y >= 0; i++)
      {
          int x = i;

          vc.pb(x * m + y);
          y--;
      }

    vc.pb(diag_l[0][0][m - 1]);

    add_xor(vc);
//    cerr << num << el;

    diag_l[1][0][m - 1] = num++;
    diag_L[n - 1][1] = num - 1;

    for (i = 1; i < n; i++)
    {
        int x = i;
        int y = m - 1;

        vi vc;
        vc.clear();

        for (; x < n && y >= 0; x++, y--)
            vc.pb(x * m + y);

        vc.pb(diag_l[0][i][m - 1]);

        add_xor(vc);
//        cerr << num << el;

        diag_l[1][i][m - 1] = num++;
        diag_L[n - i - 1][1] = num - 1;
    }

    for (j = 0; j < m - 1; j++)
    {
        int x = 0;
        int y = j;

        vi vc;
        vc.clear();

        for (; x < n && y >= 0; x++, y--)
            vc.pb(x * m + y);

        vc.pb(diag_l[0][0][j]);

        add_xor(vc);
//        cerr << num << el;

        diag_l[1][0][j] = num++;
        diag_L[n + m - j - 2][1] = num - 1;
    }

    vi vec;
//    cout << el;

    for (i = 0; i < n + m - 1 - k; i++)
    {
        vi vc, vec1;

        for (j = i; j <= i + k; j++)
        {
            vc.pb(diag_L[j][0]);
            vc.pb(diag_L[j][1]);
            vec1.pb(diag_L[j][0]);
            vec1.pb(diag_L[j][1]);
        }

        add_xor(vc);
//        cerr << num << el;
        add_not(num++);
        int hv = num++;
        add_or(vc);
        vec1.clear();
        vec1.pb(num++);
        vec1.pb(hv);
        add_and(vec1);
//        cerr << num << el;

        vec.pb(num++);
    }

    add_or(vec);
//    cerr << num << el;

    int one = num++;

    vec.clear();
    cout << el;

    for (i = 0; i < n + m - 1 - k; i++)
    {
        vi vc, vec1;
        for (j = i; j <= i + k; j++)
        {
//            cerr << diag_R[j][0] << " " << diag_R[j][1] << el;
            vc.pb(diag_R[j][0]);
            vc.pb(diag_R[j][1]);
        }

        add_xor(vc);
//        cerr << num << el;
        add_not(num++);
        int hv = num++;
        add_or(vc);
        vec1.clear();
        vec1.pb(num++);
        vec1.pb(hv);
        add_and(vec1);

        vec.pb(num++);
    }

    add_or(vec);
//    cerr << num << el;

    int two = num++;
    vec.clear();
    vec.pb(two);
    vec.pb(one);

    add_and(vec);
//    cerr << num << el << el;

    int fiv = num++;

    vec.clear();

    for (i = 0; i < n + m - 1 - k + 1; i++)
    {
        vi vc, vec1;

        for (j = i; j <= i + k - 1; j++)
        {
            vc.pb(diag_L[j][0]);
            vc.pb(diag_L[j][1]);
        }

        add_xor(vc);
//        cerr << num << el;
        add_not(num++);
        int hv = num++;
        add_or(vc);
        vec1.clear();
        vec1.pb(num++);
        vec1.pb(hv);
        add_and(vec1);

        vec.pb(num++);
    }

    add_or(vec);
//    cerr << num << el << el;

    one = num++;

    vec.clear();

    for (i = 0; i < n + m - 1 - k + 1; i++)
    {
        vi vc, vec1;
        for (j = i; j <= i + k - 1; j++)
        {
            vc.pb(diag_R[j][0]);
            vc.pb(diag_R[j][1]);
        }

        add_xor(vc);
//        cerr << num << el;
        add_not(num++);
        int hv = num++;
        add_or(vc);
        vec1.clear();
        vec1.pb(num++);
        vec1.pb(hv);
        add_and(vec1);

        vec.pb(num++);
    }

    add_or(vec);
//    cerr << num << el << el;

    two = num++;
    vec.clear();
    vec.pb(two);
    vec.pb(one);

    add_and(vec);
//    cerr << num << el << el;

    int six = num++;

    vec.clear();
    vec.pb(fiv);
    vec.pb(six);

    add_xor(vec);
//    cerr << num << el << el;

    int fst = num++;

    add_not(six);
//    cerr << num << el << el;
//    cerr << num << " " << fst << el;
    vec.clear();

    vec.pb(num++);
    vec.pb(fst);

    add_and(vec);
//    cerr << num << el << el;

    return;
}

• 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