oj.uz

Submission #403114

# Submission time Handle Problem Language Result Execution time Memory
403114 2021-05-12T19:02:01 Z rocks03 Vision Program (IOI19_vision) C++14
58 / 100
 196 ms 2916 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int add_and(vector<int> Ns);
int add_or(vector<int> Ns);
int add_xor(vector<int> Ns);
int add_not(int N);

int H, W, K;

bool valid(int x, int y){
    return (x >= 0 && x < H && y >= 0 && y < W);
}
int dist(int x, int y, int x2, int y2){
    assert(valid(x, y)); assert(valid(x2, y2));
    return abs(x - x2) + abs(y - y2);
}
int cell(int x, int y){
    assert(valid(x, y));
    return x * W + y;
}

void sub6(){
    int cnt = H * W; vector<int> answer;
    vector<int> colonna(W);
    rep(w, 0, W){
        vector<int> v;
        rep(h, 0, H){
            v.pb(cell(h, w));
        }
        add_or(v); colonna[w] = cnt++;
    }
    vector<int> tot;
    rep(w, 0, W) tot.pb(colonna[w]);
    add_xor(tot); int c0 = cnt++;

    vector<int> riga(H);
    rep(h, 0, H){
        vector<int> v;
        rep(w, 0, W){
            v.pb(cell(h, w));
        }
        add_or(v); riga[h] = cnt++;
    }

    tot.clear();
    rep(h, 0, H) tot.pb(riga[h]);
    add_xor(tot); int r0 = cnt++;

    rep(h, 1, H){
        vector<int> v;
        v = {riga[h - 1], riga[h], c0};
        add_and(v); answer.pb(cnt); cnt++;
    }
    rep(w, 1, W){
        vector<int> v;
        v = {colonna[w - 1], colonna[w], r0};
        add_and(v); answer.pb(cnt); cnt++;
    }
    add_or(answer);
}

void construct_network(int H, int W, int K){
    ::H = H, ::W = W, ::K = K;
    if(K == 1){
        sub6();
    } else{
        int cnt = H * W;
        vector<int> v;
        rep(h, 0, H){
            rep(w, 0, W){
                vector<int> v2;
                rep(h2, 0, H){
                    rep(w2, 0, W){
                        if(dist(h, w, h2, w2) == K){
                            v2.pb(cell(h2, w2));
                        }
                    }
                }
                if(!SZ(v2)) continue;
                add_or(v2);
                add_and({cell(h, w), cnt});
                cnt++;
                v.pb(cnt);
                cnt++;
            }
        }
        add_or(v);
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 284 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 296 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 9 ms 588 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 3 ms 332 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 8 ms 588 KB Output is correct
35 Correct 7 ms 460 KB Output is correct
36 Correct 5 ms 292 KB Output is correct
37 Correct 4 ms 204 KB Output is correct
38 Incorrect 196 ms 2916 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 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 292 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 296 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 292 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 296 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 300 KB Output is correct
4 Correct 51 ms 1832 KB Output is correct
5 Correct 52 ms 1284 KB Output is correct
6 Correct 40 ms 716 KB Output is correct
7 Correct 34 ms 204 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Incorrect 118 ms 2128 KB WA in grader: Too many instructions
10 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1092 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 6 ms 688 KB Output is correct
8 Correct 8 ms 716 KB Output is correct
9 Correct 11 ms 1092 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #8
0 / 19.0

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