oj.uz

Submission #612735

# Submission time Handle Problem Language Result Execution time Memory
612735 2022-07-29T22:46:30 Z CampRafael Vision Program (IOI19_vision) C++14
66 / 100
 11 ms 1492 KB 
    #include <bits/stdc++.h>
     
    void construct_network(int H, int W, int K);
     
    int add_and(std::vector<int> Ns);
     
    int add_or(std::vector<int> Ns);
     
    int add_xor(std::vector<int> Ns);
     
    int add_not(int N);
     
    int tiles[505][505];
     
    void plotar_tiles(int H,int W){
        for(int i=0;i!=H;++i){
            for(int j=0;j!=W;++j){
                tiles[i][j]=(i*W)+j;
            }
        }
    }
     
     
    ///Ideia: Caso o AND desses 2 caras sejam positivos a conexao eh invalida
    std::vector<int> gerar_lista_dist(int H,int W,int a,int b,int K){
        std::vector<int> queue;
        for(int i=0;i!=H;++i){
            for(int j=0;j!=W;++j){
                int d = abs(i-a)+abs(j-b);
                if(d==K)queue.push_back(tiles[i][j]);
            }
        }
        return queue;
    }
     
    bool ok[505][505]={};
    void construct_network(int H, int W, int K) {
        plotar_tiles(H,W);
    	///Min(H,W) == 1
    	if(std::min(H,W)==1){
            if(H==1){
                int count=0;
                for(int i=0;i!=W;++i){
                    int esperado = i+K;
                    if(esperado>=W)break;
                    std::vector<int> v;
                    v.push_back(tiles[0][i]);
                    v.push_back(tiles[0][esperado]);
                    add_and(v);
                    ++count;
                }
                std::vector<int> orzao;
                for(int i=0;i!=count;++i)orzao.push_back(H*W+i);
                add_or(orzao);
            }else {
                assert(W==1);
                int count=0;
                for(int i=0;i!=H;++i){
                    int esperado = i+K;
                    if(esperado>=H)break;
                    std::vector<int> v;
                    v.push_back(tiles[i][0]);
                    v.push_back(tiles[esperado][0]);
                    add_and(v);
                    ++count;
                }
                std::vector<int> orzao;
                for(int i=0;i!=count;++i)orzao.push_back(H*W+i);
                add_or(orzao);
            }
    	}else if(std::max(H,W)<=31){
    	    int count=0;
            for(int i=0;i!=H;++i){
                for(int j=0;j!=W;++j){
                    std::vector<int> res = gerar_lista_dist(H,W,i,j,K);
                    if(!res.size())continue;
                    ok[i][j]=1;
                    add_or(res);
                    ++count;
                }
            }
            std::vector<int> orzao;
            int anda=0;
            for(int i=0;i!=H;++i){
                for(int j=0;j!=W;++j){
                    if(!ok[i][j])continue;
                    std::vector<int> res;
                    res.push_back(tiles[i][j]);
                    res.push_back(H*W+anda);
                    ++anda;
                    add_and(res);
                    orzao.push_back(H*W+count);
                    ++count;
                }
            }
            add_or(orzao);
    	}else if(K==1){
            std::vector<int> k,g;
    	    {
    	        std::vector<int> listaxorzao;
                for(int i=0;i!=H;++i){
                    std::vector<int> l;
                    for(int j=0;j!=W;++j){
                        l.push_back(tiles[i][j]);
                    }
                    listaxorzao.push_back(add_or(l));
                }
                k.push_back(add_xor(listaxorzao));
                std::vector<int> kok;
                for(int i=0;i!=H-1;++i){
                    std::vector<int> adj;
                    adj.push_back(listaxorzao[i]);
                    adj.push_back(listaxorzao[i+1]);
                    kok.push_back(add_and(adj));
                }
                g.push_back(add_or(kok));
    	    }
     
    	    {
    	        std::vector<int> listaxorzao;
                for(int j=0;j!=W;++j){
                    std::vector<int> l;
                    for(int i=0;i!=H;++i){
                        l.push_back(tiles[i][j]);
                    }
                    listaxorzao.push_back(add_or(l));
                }
                k.push_back(add_xor(listaxorzao));
                std::vector<int> kok;
                for(int i=0;i!=W-1;++i){
                    std::vector<int> adj;
                    adj.push_back(listaxorzao[i]);
                    adj.push_back(listaxorzao[i+1]);
                    kok.push_back(add_and(adj));
                }
                g.push_back(add_or(kok));
    	    }
    	    int c=add_and({k[0],g[1]}),d=add_and({k[1],g[0]});
    	    add_or({c,d});
        }else{///Pixel no canto superior esquerdo
            std::vector<int> lista;
            for(int i=0;i!=H;++i)
                for(int j=0;j!=W;++j){
                    if(i+j==K){
                        lista.push_back(tiles[i][j]);
                    }
                }
            add_or(lista);
    	}
    }

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 0 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 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 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 1 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 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 0 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 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 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 1 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 0 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 340 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 0 ms 340 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 0 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 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 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 1 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 0 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 340 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 6 ms 724 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 2 ms 340 KB Output is correct
33 Correct 2 ms 448 KB Output is correct
34 Correct 5 ms 724 KB Output is correct
35 Correct 5 ms 596 KB Output is correct
36 Correct 3 ms 468 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 0 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 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 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 1 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 0 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 340 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 6 ms 724 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 2 ms 340 KB Output is correct
33 Correct 2 ms 448 KB Output is correct
34 Correct 5 ms 724 KB Output is correct
35 Correct 5 ms 596 KB Output is correct
36 Correct 3 ms 468 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Incorrect 0 ms 468 KB on inputs (8, 61), (22, 97), expected 1, but computed 0
39 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.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 596 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 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 1 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 1 ms 724 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 0 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 596 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 1 ms 468 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 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 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 5 ms 1108 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 0 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 5 ms 880 KB Output is correct
25 Correct 0 ms 468 KB Output is correct
26 Correct 0 ms 468 KB Output is correct
27 Correct 8 ms 1448 KB Output is correct
28 Correct 0 ms 596 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 0 ms 596 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1492 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 4 ms 1108 KB Output is correct
8 Correct 4 ms 852 KB Output is correct
9 Correct 11 ms 1452 KB Output is correct
10 Correct 0 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 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 0 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 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 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 1 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 0 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 340 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 6 ms 724 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 2 ms 340 KB Output is correct
33 Correct 2 ms 448 KB Output is correct
34 Correct 5 ms 724 KB Output is correct
35 Correct 5 ms 596 KB Output is correct
36 Correct 3 ms 468 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Incorrect 0 ms 468 KB on inputs (8, 61), (22, 97), expected 1, but computed 0
39 Halted 0 ms 0 KB -