oj.uz

Submission #817189

# Submission time Handle Problem Language Result Execution time Memory
817189 2023-08-09T10:23:16 Z Pikachu Vision Program (IOI19_vision) C++17
66 / 100
 16 ms 1964 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()
{
    vector<int> tmp;
    if (n == 1) {
        for (int j = 0; j + k < m; j++) {
            tmp.push_back(add_and({getIndex(0, j), getIndex(0, j + k)}));
        }
    }
    else {
        for (int i = 0; i + k < n; i++) {
            tmp.push_back(add_and({getIndex(i, 0), getIndex(i + k, 0)}));
        }
    }
    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};

int rownot[maxn];
int colnot[maxn];

void solvek1()
{
    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);
        rownot[i] = add_not(row[i]);
    }

    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);
        colnot[j] = add_not(col[j]);
    }

    int onerow, onecol;
    vector<int> dak;
    for (int i = 0; i < n; i++) {
        vector<int> tmp;
        for (int j = 0; j < n; j++) {
            if (i == j) tmp.push_back(row[j]);
            else tmp.push_back(rownot[j]);
        }
        dak.push_back(add_and(tmp));
    }
    onerow = add_or(dak);

    dak.clear();
    for (int i = 0; i < m; i++) {
        vector<int> tmp;
        for (int j = 0; j < m; j++) {
            if (i == j) tmp.push_back(col[j]);
            else tmp.push_back(colnot[j]);
        }
        dak.push_back(add_and(tmp));
    }
    onecol = add_or(dak);

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

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 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 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 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 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 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #2
11.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 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 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 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 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct

Subtask #3
11.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 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 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 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 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 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 296 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 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 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 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 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 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 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 296 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
12.0 / 12.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 1 ms 212 KB Output is correct
4 Correct 0 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 0 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 0 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 1 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 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct

Subtask #6
8.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 Correct 2 ms 480 KB Output is correct
4 Correct 1 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 0 ms 212 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 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 8 ms 1236 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 8 ms 1272 KB Output is correct
25 Correct 1 ms 256 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 14 ms 1876 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1876 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 8 ms 1220 KB Output is correct
8 Correct 8 ms 1236 KB Output is correct
9 Correct 16 ms 1964 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 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 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 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 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 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 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 296 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 -