Submission #1046778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046778		boyliguanhan	Vision Program (IOI19_vision)	C++17	100 / 100	13 ms	3356 KiB

vision

#include "vision.h"
using namespace std;
int ZERO,ONE;
typedef vector<int> VI;
VI whatsdis(VI bits){
    int n=bits.size();
    VI res;
    for(int i=0;i<8;i++){
        VI pos;
        for(int j=1;j<n;j++)
            if(j>>i&1)
                pos.push_back(j);
        VI to_or;
        for(int i=0;i<n;i++){
            VI stuf;
            for(auto k:pos)
                if(k+i<n)
                    stuf.push_back(bits[k+i]);
            if(stuf.size())
                to_or.push_back(add_and({bits[i],add_or(stuf)}));
        }
        res.push_back(to_or.empty()?ZERO:add_or(to_or));
    }
    return res;
}
VI add_bits(VI A,VI B){
    while(A.size()<8)
        A.push_back(0);
    while(B.size()<8)
        B.push_back(0);
    int CAR=ZERO;
    VI res;
    for(int i=0;i<8;i++){
        res.push_back(add_xor({CAR,A[i],B[i]}));
        CAR=add_or({add_and({A[i],B[i]}),add_and({A[i],CAR}),add_and({B[i],CAR})});
    }
    res.push_back(CAR);
    return res;
}
void check_if_same(VI bits,int num){
    VI finale;
    for(int i=0;i<9;i++)
        finale.push_back(add_xor({bits[i],num&1<<i?ZERO:ONE}));
    add_and(finale);
}
void construct_network(int H, int W, int K) {
    if(H*W==2) return void(add_and({0,1}));
    ZERO=add_and({0,1,2});
    ONE=add_not(ZERO);
    vector<VI> rows(H),cols(W);
    for(int i=0;i<H;i++)
        for(int j=0;j<W;j++)
            rows[i].push_back(i*W+j),
            cols[j].push_back(i*W+j);
    VI R,C;
    for(int i=0;i<H;i++)
        R.push_back(add_or(rows[i]));
    for(int i=0;i<W;i++)
        C.push_back(add_or(cols[i]));
    VI bits1=whatsdis(C),bits2=whatsdis(R);
    VI bits3=add_bits(bits1,bits2);
    check_if_same(bits3,K);
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 15 / 15
• Subtask 5: 12 / 12
• Subtask 6: 8 / 8
• Subtask 7: 14 / 14
• Subtask 8: 19 / 19