oj.uz

Submission #658936

# Submission time Handle Problem Language Result Execution time Memory
658936 2022-11-15T12:58:49 Z jiahng Vision Program (IOI19_vision) C++14
26 / 100
 18 ms 3024 KB 
#include "vision.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 201
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;

int H,W;
bool valid(int x,int y){
    return (x >= 0 && x < H && y >= 0 && y < W);
}
int ordiag1[maxn][maxn],ordiag2[maxn][maxn],xordiag1[maxn][maxn],xordiag2[maxn][maxn];
void construct_network(int H, int W, int K) {
    vi ans;
    ::H = H; ::W = W;
    // precomp OR and XOR in each diagonal
    for (int si=0,sj=W-1;si<H;(sj==0?si++:sj--)){
        vi v;
        for (int i=si,j=sj;valid(i,j);i++,j++) v.pb(i*W+j);
        ordiag1[si][sj] = add_or(v);
        xordiag1[si][sj] = add_xor(v);
    }

    for (int si=0,sj=0;si<H;(sj==W-1?si++:sj++)){ // antidiagonal
        vi v;
        for (int i=si,j=sj;valid(i,j);i++,j--) v.pb(i*W+j);
        ordiag2[si][sj] = add_or(v);
        xordiag2[si][sj] = add_xor(v);
    }

    vi axis1_unstrict_or, axis2_strict_or;
    for (int si=0,sj=W-1;si<H;(sj==0?si++:sj--)){
        vi orv,xorv;
        for (int k=0;k<=K;k++){
            int diagi = si+k, diagj = sj;
            diagi -= diagj; diagj = 0;

            if (!valid(diagi, diagj)){
                diagj -= diagi; diagi = 0;
            }
            if (!valid(diagi, diagj)) continue;
            assert(diagi == 0 || diagj == 0);
            orv.pb(ordiag1[diagi][diagj]);
            xorv.pb(xordiag1[diagi][diagj]);
        }
        if (orv.empty()) continue;
        axis1_unstrict_or.pb(add_and({add_or(orv), add_not(add_xor(xorv))}));
    }
    int distleqK1 = add_or(axis1_unstrict_or);
    for (int si=0,sj=0;si<H;(sj==W-1?si++:sj++)){
        int diagi = si+K, diagj = sj;
        diagj += diagi; diagi = 0;
        if (!valid(diagi, diagj)){
            diagi -= (-diagj + W - 1);
            diagj = W-1; 
        }
        if (!valid(diagi, diagj)) continue;
        int or_idx = add_or({ordiag2[diagi][diagj], ordiag2[si][sj]});
        int xor_idx = add_xor({xordiag2[diagi][diagj], xordiag2[si][sj]});
        axis2_strict_or.pb(add_and({or_idx, add_not(xor_idx)})); // Whether it is distance K on the axis
    }
    int distK2 = add_or(axis2_strict_or);
    int ok1 = add_and({distleqK1, distK2});

    vi axis2_unstrict_or, axis1_strict_or;

    for (int si=0,sj=0;si<H;(sj==W-1?si++:sj++)){ // antidiagonal
        vi orv,xorv;
        for (int k=0;k<=K;k++){
            int diagi = si+k, diagj = sj;
            diagj += diagi; diagi = 0;
            if (!valid(diagi, diagj)){
                diagi -= (-diagj + W - 1);
                diagj = W-1;
            }
            if (!valid(diagi, diagj)) continue;

            orv.pb(ordiag2[diagi][diagj]);
            xorv.pb(xordiag2[diagi][diagj]);
        }
        axis2_unstrict_or.pb(add_and({add_or(orv), add_not(add_xor(xorv))}));
    }
    int distleqK2 = add_or(axis2_unstrict_or);

    for (int si=0,sj=W-1;si<H;(sj==0?si++:sj--)){ // diagonal
        int diagi = si+K, diagj = sj;
        diagj -= diagi; diagi = 0;
        if (!valid(diagi, diagj)){
            diagi -= diagj;
            diagj = 0;
        }
        if (!valid(diagi, diagj)) continue;
        int or_idx = add_or({ordiag1[diagi][diagj], ordiag1[si][sj]});
        int xor_idx = add_xor({xordiag1[diagi][diagj], xordiag1[si][sj]});
        axis1_strict_or.pb(add_and({or_idx, add_not(xor_idx)})); // Whether it is distance K on the axis
    }
    int distK1 = add_or(axis1_strict_or);
    int ok2 = add_and({distleqK2, distK1});
    
    add_or({ok1, ok2});
}

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 0 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 0 ms 304 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 0 ms 304 KB on inputs (0, 1), (1, 0), expected 0, but computed 1
16 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 0 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 0 ms 304 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 0 ms 304 KB on inputs (0, 1), (1, 0), expected 0, but computed 1
16 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 0 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 0 ms 304 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 0 ms 304 KB on inputs (0, 1), (1, 0), expected 0, but computed 1
16 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 0 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 0 ms 304 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 0 ms 304 KB on inputs (0, 1), (1, 0), expected 0, but computed 1
16 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 8 ms 944 KB Output is correct
3 Correct 9 ms 940 KB Output is correct
4 Correct 9 ms 1100 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 6 ms 1492 KB Output is correct
7 Correct 9 ms 1620 KB Output is correct
8 Correct 10 ms 1764 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 5 ms 852 KB Output is correct
11 Correct 7 ms 980 KB Output is correct
12 Correct 7 ms 1052 KB Output is correct
13 Correct 8 ms 1064 KB Output is correct
14 Correct 8 ms 1168 KB Output is correct
15 Correct 2 ms 1236 KB Output is correct
16 Correct 5 ms 1492 KB Output is correct
17 Correct 8 ms 1588 KB Output is correct
18 Correct 8 ms 1608 KB Output is correct
19 Correct 8 ms 1716 KB Output is correct
20 Correct 8 ms 1720 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 308 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 3 ms 852 KB Output is correct
4 Incorrect 4 ms 980 KB on inputs (0, 0), (15, 15), expected 0, but computed 1
5 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3024 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 4 ms 948 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 3 ms 1224 KB Output is correct
7 Correct 10 ms 2128 KB Output is correct
8 Correct 11 ms 1808 KB Output is correct
9 Correct 18 ms 2992 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 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 0 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 0 ms 304 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 0 ms 304 KB on inputs (0, 1), (1, 0), expected 0, but computed 1
16 Halted 0 ms 0 KB -