Submission #731687

#	Time	Username	Problem	Language	Result	Execution time	Memory
731687		danikoynov	Vision Program (IOI19_vision)	C++14	0 / 100	67 ms	7216 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
using namespace std;

int H, W;

bool valid_cell(int x, int y)
{
    if (x >= 0 && x < H &&
        y >= 0 && y < W)
            return true;
    return false;
}

int left_diagonal_one(int sum)
{
    vector < int > cells;
    for (int x = 0; x < H; x ++)
    {
        int y = sum - x;
        if (valid_cell(x, y))
        {
            cells.push_back(x * W + y);
        }
    }
    /**cout << "query one " << endl;
    for (int v : cells)
    {
        cout << v / M << " " << v % M << endl;
    }*/

    return add_or(cells);
}

int left_diagonal_two(int sum)
{
    vector < int > cells;
    for (int x = 0; x < H; x ++)
    {
        int y = sum - x;
        if (valid_cell(x, y))
        {
            cells.push_back(x * W + y);
        }
    }

    int f1 = add_or(cells), f2 = add_xor(cells);
    int f3 = add_not(f2);
    vector < int > fin;
    fin.push_back(f1);
    fin.push_back(f3);
    return add_and(fin);
}

int right_diagonal_one(int diff)
{
    vector < int > cells;
    for (int x = 0; x < H; x ++)
    {
        int y = x + diff;
        if (valid_cell(x, y))
        {
            cells.push_back(x * W + y);
        }
    }
    /**cout << "query one " << endl;
    for (int v : cells)
    {
        cout << v / M << " " << v % M << endl;
    }*/

    return add_or(cells);
}

int right_diagonal_two(int diff)
{
    vector < int > cells;
    for (int x = 0; x < H; x ++)
    {
        int y = x + diff;
        if (valid_cell(x, y))
        {
            cells.push_back(x * W + y);
        }
    }

    int f1 = add_or(cells), f2 = add_xor(cells);
    int f3 = add_not(f2);
    vector < int > fin;
    fin.push_back(f1);
    fin.push_back(f3);
    return add_and(fin);
}

const int maxn = 1000;
int dig[2][2][maxn * 2];

void build_diagonals()
{
    for (int diff = W - 1; diff >= - H + 1; diff --)
    {
        dig[0][0][diff + maxn] = right_diagonal_one(diff);
        dig[1][0][diff + maxn] = right_diagonal_two(diff);
    }

    for (int sum = 0; sum <= H + W - 2; sum ++)
    {
        dig[0][1][sum + maxn] = left_diagonal_one(sum);
        dig[1][1][sum + maxn] = left_diagonal_two(sum);
    }
}

int get_right_gate(int dis)
{
    vector < int > con;
    for (int diff = W - 1; diff >= - H + 1; diff --)
    {
        vector < int > var, double_row;
        for (int cur = diff; cur >= - H + 1 && var.size() <= dis; cur --)
        {
            int v1 = dig[0][0][cur + maxn], v2 = dig[1][0][cur + maxn];
            double_row.push_back(v2);
            var.push_back(v1);
        }
        if (var.size() <= dis)
            break;

        int atl = add_or(var);
        int xort = add_xor(var);
        xort = add_not(xort);
        vector < int > mg;
        mg.push_back(atl);
        mg.push_back(xort);
        int comb = add_and(mg), is_double = add_or(double_row);
        mg.clear();
        mg.push_back(comb);
        mg.push_back(is_double);
        con.push_back(add_or(mg));
    }
    return add_or(con);
}

int get_left_gate(int dis)
{
    vector < int > con;
    for (int sum = 0; sum <= H + W - 2; sum ++)
    {
        vector < int > var, double_row;
        for (int cur = 0; cur <= H + W - 2 && var.size() <= dis; cur ++)
        {
            int v1 = dig[0][1][cur + maxn], v2 = dig[1][1][cur + maxn];
            double_row.push_back(v2);
            var.push_back(v1);
        }
        if (var.size() <= dis)
            break;

        int atl = add_or(var);
        int xort = add_xor(var);
        xort = add_not(xort);
        vector < int > mg;
        mg.push_back(atl);
        mg.push_back(xort);
        int comb = add_and(mg), is_double = add_or(double_row);
        mg.clear();
        mg.push_back(comb);
        mg.push_back(is_double);
        con.push_back(add_or(mg));
    }
    return add_or(con);
}
int check(int dis)
{
    int gate_right = get_right_gate(dis);

    int gate_left = get_left_gate(dis);

    vector < int > fin;
    fin.push_back(gate_left);

    fin.push_back(gate_right);
    return add_and(fin);
}
void construct_network(int h, int w, int K)
{
    H = h;
    W = w;


    build_diagonals();
    if (K == 1)
    {
        int is_less = check(K);
        return;
    }
    int is_above = check(K - 1);

    int is_less = check(K);

    int not_above = add_not(is_above);
    vector < int > fin;
    fin.push_back(not_above);
    fin.push_back(is_less);
    add_and(fin);

}

Compilation message (stderr)

vision.cpp: In function 'int get_right_gate(int)':
vision.cpp:119:59: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  119 |         for (int cur = diff; cur >= - H + 1 && var.size() <= dis; cur --)
      |                                                ~~~~~~~~~~~^~~~~~
vision.cpp:125:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |         if (var.size() <= dis)
      |             ~~~~~~~~~~~^~~~~~
vision.cpp: In function 'int get_left_gate(int)':
vision.cpp:149:58: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  149 |         for (int cur = 0; cur <= H + W - 2 && var.size() <= dis; cur ++)
      |                                               ~~~~~~~~~~~^~~~~~
vision.cpp:155:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  155 |         if (var.size() <= dis)
      |             ~~~~~~~~~~~^~~~~~
vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:193:13: warning: unused variable 'is_less' [-Wunused-variable]
  193 |         int is_less = check(K);
      |             ^~~~~~~

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