Submission #612735

#	Time	Username	Problem	Language	Result	Execution time	Memory
612735		CampRafael	Vision Program (IOI19_vision)	C++14	66 / 100	11 ms	1492 KiB

vision

    #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 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 0 / 15
• Subtask 5: 12 / 12
• Subtask 6: 8 / 8
• Subtask 7: 14 / 14
• Subtask 8: 0 / 19