oj.uz

Submission #573888

# Submission time Handle Problem Language Result Execution time Memory
573888 2022-06-07T11:27:28 Z Stickfish Vision Program (IOI19_vision) C++17
12 / 100
 32 ms 4436 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;
    //return diag_check;
    vector<vector<bool>> used(h, vector<bool>(w, false));
    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;
                for (int j0 = j; j0 < w; j0 += 2 * k) {
                    for (int j1 = j0; j1 < j0 + k && j1 < w; ++j1) {
                        start.push_back(cr.get_num(i, j1));
                        used[i][j1] = true;
                        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)));
                        }
                    }
                }
                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);
                ++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:87:9: warning: unused variable 'cnt' [-Wunused-variable]
   87 |     int cnt = h * w;
      |         ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 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 296 KB Output is correct
7 Incorrect 1 ms 300 KB on inputs (0, 2), (1, 0), expected 0, but computed 1
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 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 296 KB Output is correct
7 Incorrect 1 ms 300 KB on inputs (0, 2), (1, 0), expected 0, but computed 1
8 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 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 296 KB Output is correct
7 Incorrect 1 ms 300 KB on inputs (0, 2), (1, 0), expected 0, but computed 1
8 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 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 296 KB Output is correct
7 Incorrect 1 ms 300 KB on inputs (0, 2), (1, 0), expected 0, but computed 1
8 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 304 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 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 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 1 ms 428 KB Output is correct
17 Correct 1 ms 424 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 272 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 4 ms 556 KB Output is correct
4 Correct 8 ms 1072 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 4 ms 552 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 8 ms 852 KB Output is correct
9 Correct 22 ms 2380 KB Output is correct
10 Correct 13 ms 1644 KB Output is correct
11 Correct 6 ms 852 KB Output is correct
12 Correct 3 ms 428 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 23 ms 2136 KB Output is correct
21 Incorrect 8 ms 4436 KB WA in grader: Too many inputs
22 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 3880 KB on inputs (14, 10), (15, 8), expected 0, but computed 1
2 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 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 296 KB Output is correct
7 Incorrect 1 ms 300 KB on inputs (0, 2), (1, 0), expected 0, but computed 1
8 Halted 0 ms 0 KB -