oj.uz

Submission #817182

# Submission time Handle Problem Language Result Execution time Memory
817182 2023-08-09T10:12:35 Z Pikachu Vision Program (IOI19_vision) C++17
32 / 100
 1 ms 1104 KB 
#include <bits/stdc++.h>
#include "vision.h"

using namespace std;


const int maxprime = 46;
int prime[46] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199};

const int maxn = 210;
int n, m, k;
int row[maxn];
int col[maxn];
int row2[maxn];
int col2[maxn];

int getIndex(int x, int y)
{
    return x * m + y;
};

void solvemax100()
{
    for (int i = 0; i < n; i++) {
        vector<int> tmp;
        for (int j = 0; j < m; j++) {
            tmp.push_back(getIndex(i, j));
        }
        row[i] = add_or(tmp);
    }

    for (int j = 0; j < m; j++) {
        vector<int> tmp;
        for (int i = 0; i < n; i++) {
            tmp.push_back(getIndex(i, j));
        }
        col[j] = add_or(tmp);
    }

    for (int i = 1; i < n; i++) {
        vector<int> tmp;
        for (int j = 0; j + i < n; j++) {
            tmp.push_back(add_and({row[j], row[j + i]}));
        }
        row2[i] = (int)tmp.size() == 1 ? tmp.back() : add_or(tmp);
    }
    row2[0] = (n == 1) ? -1 : add_not(add_or(vector<int>(row2 + 1, row2 + n)));
    
    for (int i = 1; i < m; i++) {
        vector<int> tmp;
        for (int j = 0; j + i < m; j++) {
            tmp.push_back(add_and({col[j], col[j + i]}));
        }
        col2[i] = (int)tmp.size() == 1 ? tmp.back() : add_or(tmp);
    }
    col2[0] = (m == 1) ? -1 : add_not(add_or(vector<int>(col2 + 1, col2 + m)));

    vector<int> tmp;
    for (int i = 0; i <= min(n - 1, k); i++) {
        int j = k - i;
        if (!(0 <= j && j < m)) continue;
        if (row2[i] == -1) tmp.push_back(col2[j]);
        else if (col2[j] == -1) tmp.push_back(row2[i]); 
        else tmp.push_back(add_and({row2[i], col2[j]}));
    }

    add_or(tmp);
}

void solvemin1()
{
    for (int i = 0; i < n; i++) {
        vector<int> tmp;
        for (int j = 0; j < m; j++) {
            tmp.push_back(getIndex(i, j));
        }
        row[i] = add_or(tmp);
    }

    for (int j = 0; j < m; j++) {
        vector<int> tmp;
        for (int i = 0; i < n; i++) {
            tmp.push_back(getIndex(i, j));
        }
        col[j] = add_or(tmp);
    }

    vector<int> tmp;
    for (int i = 1; i < n; i++) {
        tmp.push_back(add_and({row[i - 1], row[i]}));
    }
    
    for (int i = 1; i < m; i++) {
        tmp.push_back(add_and({col[i - 1], col[i]}));
    } 
    
    add_or(tmp);
}

bool check(int i, int j) { return (0 <= i && i < n && 0 <= j && j < m); }

void solve00()
{
    vector<int> tmp;
    for (int i = 0; i <= k; i++) {
        int j = k - i;
        if (!check(i, j)) continue;
        tmp.push_back(getIndex(i, j));
    }
    add_or(tmp);
}

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

void solvek1()
{
    vector<int> tmp;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int d = 0; d < 4; d++) {
                int x = i + dx[d];
                int y = j + dy[d];
                if (!check(x, y)) continue;
                tmp.push_back(add_and({getIndex(i, j), getIndex(x, y)}));
            }
        }
    }
    add_or(tmp);
}

void construct_network(int n, int m, int k) 
{
    ::n = n;
    ::m = m;
    ::k = k;
    if (max(n, m) <= 100) solvemax100();
    else if (min(n, m) == 1) solvemin1();
    else if (k == 1) solvek1();
    else solve00();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Incorrect 1 ms 1104 KB WA in grader: Too many instructions
39 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 0 ms 212 KB on inputs (0, 0), (0, 1), expected 0, but computed 1
3 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 1104 KB WA in grader: Too many instructions
4 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1104 KB WA in grader: Too many instructions
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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Incorrect 1 ms 1104 KB WA in grader: Too many instructions
39 Halted 0 ms 0 KB -