oj.uz

Submission #573923

# Submission time Handle Problem Language Result Execution time Memory
573923 2022-06-07T12:22:06 Z Stickfish Vision Program (IOI19_vision) C++17
26 / 100
 48 ms 5684 KB 
#include "vision.h"
#include <functional>
#include <iostream>
using namespace std;

int memsz;

struct cords {
    bool rvs;
    int h;
    int w;

    int get_num(int i, int j) const {
        if (rvs)
            j = w - j - 1;
        return i * w + j;
    }
};

int get_downright(int h, int w, int k, cords cr) {
    vector<vector<int>> diags(w + h - 1);
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            diags[i + j].push_back(cr.get_num(i, j));
        }
    }
    vector<int> diag_nums;
    for (int i = 0; i < h + w - 1; ++i) {
        add_xor(diags[i]);
        diag_nums.push_back(memsz);
        ++memsz;
    }
    vector<int> diag_pairs;
    for (int i = 0; i + k < h + w - 1; ++i) {
        add_and({diag_nums[i], diag_nums[i + k]});
        diag_pairs.push_back(memsz);
        ++memsz;
    }
    add_or(diag_pairs);
    int diag_check = memsz;
    ++memsz;
    vector<vector<bool>> used(h, vector<bool>(w, false));
    vector<vector<int>> end_mem(h, vector<int>(w, -1));
    vector<int> direction_check;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (!used[i][j]) {
                vector<int> start;
                vector<int> end;
                if (i)
                    end.push_back(end_mem[i - 1][j]);
                for (int j0 = j; j0 < w; j0 += 3 * k) {
                    for (int j1 = j0; j1 < j0 + k && j1 < w; ++j1) {
                        start.push_back(cr.get_num(i, j1));
                        used[i][j1] = true;
                        if (i == 0) {
                            for (int i1 = i; i1 < h && i1 <= i + k; ++i1) {
                                if (j1 + k - (i1 - i) < w)
                                    end.push_back(cr.get_num(i1, j1 + k - (i1 - i)));
                            }
                        } else {
                            if (j1 + k < w)
                                end.push_back(cr.get_num(i - 1, j1 + k));
                            if (i + k < h)
                                end.push_back(cr.get_num(i + k, j1));
                            int t = (j0 + k - j1) - 1;
                            if (i + t < h) {
                                end.push_back(cr.get_num(i + t, j1));
                                if (j1 + k < w)
                                    end.push_back(cr.get_num(i + t, j1 + k));
                            }
                        }
                    }
                }
                if (start.empty() || end.empty())
                    continue;
                //for (auto x : start)
                    //cout << x << ' ';
                //cout << "| ";
                //for (auto x : end)
                    //cout << x << ' ';
                //cout << endl;
                add_xor(start);
                ++memsz;
                add_xor(end);
                end_mem[i][j] = memsz;
                ++memsz;
                add_and({memsz - 2, memsz - 1});
                direction_check.push_back(memsz);
                ++memsz;
            }
        }
    }
    add_or(direction_check);
    ++memsz;
    add_and({memsz - 1, diag_check});
    ++memsz;
    return memsz - 1;
}


void construct_network(int h, int w, int k) {
    int cnt = h * w;
    memsz = h * w;
    cords c;
    c.rvs = 0;
    c.h = h;
    c.w = w;
    int ans0 = get_downright(h, w, k, c);
    c.rvs = 1;
    int ans1 = get_downright(h, w, k, c);
    if (ans0 == -1)
        return;
    if (ans1 == -1) {
        add_and({ans0});
        return;
    }
    add_or({ans0, ans1});
}

Compilation message

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:103:9: warning: unused variable 'cnt' [-Wunused-variable]
  103 |     int cnt = h * w;
      |         ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB WA in grader: Invalid index
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB WA in grader: Invalid index
9 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB WA in grader: Invalid index
9 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB WA in grader: Invalid index
9 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 3 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 2 ms 428 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 6 ms 808 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 424 KB Output is correct
8 Correct 8 ms 980 KB Output is correct
9 Correct 8 ms 852 KB Output is correct
10 Incorrect 1 ms 340 KB WA in grader: Invalid index
11 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5656 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 5 ms 724 KB Output is correct
4 Correct 8 ms 980 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 30 ms 3104 KB Output is correct
8 Correct 28 ms 2964 KB Output is correct
9 Correct 46 ms 5684 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 300 KB Output is correct

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB WA in grader: Invalid index
9 Halted 0 ms 0 KB -