Submission #626186

#	Time	Username	Problem	Language	Result	Execution time	Memory
626186		TimDee	Vision Program (IOI19_vision)	C++17	0 / 100	11 ms	1488 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
using namespace std;

void construct_network(int h, int w, int k) {

    if (h*w==2) {
        if (k==1) add_and({0,1});
        else add_xor({0,1});
        return;
    }

    int zero = add_and({0,1,2});
    int one = add_not(zero);

    vector<int> row(h,0);
    vector<int> col(w,0);

    for (int i=0; i<h; ++i) {
        vector<int> a;
        for (int j=0; j<w; ++j) {
            a.push_back(i*w+j);
        }
        row[i]=add_xor(a);
    }
    for (int j=0; j<w; ++j) {
        vector<int> a;
        for (int i=0; i<h; ++i) {
            a.push_back(i*w+j);
        }
        col[j]=add_xor(a);
    }
    int _check1 = add_or(row), _check2 = add_or(col);
    int check1 = add_not(_check1), check2 = add_not(_check2);
    vector<int> row_k={zero}, col_k={zero};
    for (int j=0; j+k<w; ++j) col_k.push_back(add_and({col[j],col[j+k]}));
    for (int i=0; i+k<h; ++i) row_k.push_back(add_and({row[i],row[i+k]}));

    int _a1=add_or(col_k), _a2=add_or(row_k);
    int inSameRow=add_and({check1,_a1}), inSameCol=add_and({check2,_a2});

    vector<int> prefRow, sufRow, prefCol, sufCol;
    prefRow={row[0]};
    for (int i=1; i<h; ++i) {
        prefRow.push_back(add_xor({row[i],prefRow[i-1]}));
    }
    sufRow={row[h-1]};
    for (int i=h-2; i>=0; --i) {
        sufRow.push_back(add_xor({row[i],sufRow[h-2-i]}));
    }
    prefCol={col[0]};
    for (int i=1; i<w; ++i) {
        prefCol.push_back(add_xor({col[i],prefCol[i-1]}));
    }
    sufCol={col[w-1]};
    for (int i=w-2; i>=0; --i) {
        sufCol.push_back(add_xor({col[i],sufCol[w-2-i]}));
    }

    vector<int> bitxl, bityl, bitxr, bityr;
    vector<int> rl(h), cl(w), rr(h), cr(w);

    for (int i=0; i<h; ++i) {
        //cout<<"PrefRow\n";
        int p=add_and({i?prefRow[i-1]:zero,(i<(h-1))?prefRow[i+1]:zero});
        int q=add_xor({p,prefRow[i],i?prefRow[i-1]:zero});
        int t=add_not(p);
        rl[i]=add_and({q,prefRow[i],t});
    }
    for (int i=0; i<h; ++i) {
        //cout<<"SufRow\n";
        int p=add_and({i?sufRow[i-1]:zero,(i<(h-1))?sufRow[i+1]:zero});
        int q=add_xor({p,sufRow[i],i?sufRow[i-1]:zero});
        int t=add_not(p);
        rr[h-1-i]=add_and({q,sufRow[i],t});
    }
    for (int i=0; i<w; ++i) {
        //cout<<"PrefCol\n";
        int p=add_and({i?prefCol[i-1]:zero,(i<(w-1))?prefCol[i+1]:zero});
        int q=add_xor({p,prefCol[i],i?prefCol[i-1]:zero});
        int t=add_not(p);
        cl[i]=add_and({q,prefCol[i],t});
    }
    for (int i=0; i<w; ++i) {
        //cout<<"SufCol\n";
        int p=add_and({i?sufCol[i-1]:zero,(i<(w-1))?sufCol[i+1]:zero});
        int q=add_xor({p,sufCol[i],i?sufCol[i-1]:zero});
        int t=add_not(p);
        cr[w-1-i]=add_and({q,sufCol[i],t});
    }

    for (int i=0; (1<<i)<h; ++i) {
        vector<int> a;
        for (int x=0; x<h; ++x) {
            if ((x>>i) & 1) a.push_back(rl[x]);
        }
        bitxl.push_back(add_or(a));
    } //for (auto x:bitxl) cout<<x<<' '; cout<<'\n';
    for (int i=0; (1<<i)<w; ++i) {
        vector<int> a;
        for (int x=0; x<w; ++x) {
            if ((x>>i) & 1) a.push_back(cl[x]);
        }
        bityl.push_back(add_or(a));
    } //for (auto x:bityl) cout<<x<<' '; cout<<'\n';
    for (int i=0; (1<<i)<h; ++i) {
        vector<int> a;
        for (int x=0; x<h; ++x) {
            if ((x>>i) & 1) a.push_back(rr[x]);
        }
        bitxr.push_back(add_or(a));
    } //for (auto x:bitxr) cout<<x<<' '; cout<<'\n';
    for (int i=0; (1<<i)<w; ++i) {
        vector<int> a;
        for (int x=0; x<w; ++x) {
            if ((x>>i) & 1) a.push_back(cr[x]);
        }
        bityr.push_back(add_or(a));
    } //for (auto x:bityr) cout<<x<<' '; cout<<'\n';

    vector<int> xorx(10,zero),xory(10,zero),ansbitx(10,zero),ansbity(10,zero),ansbit(10,zero);
    for (int i=0; (1<<i)<h; ++i) {
        xorx[i]=add_xor({bitxl[i],bitxr[i]});
    }
    for (int i=0; (1<<i)<w; ++i) {
        xory[i]=add_xor({bityl[i],bityr[i]});
    }
    ansbitx[0]=xorx[0];
    ansbity[0]=xory[0];
    for (int i=1; (1<<i)<h; ++i) {
        int q=add_not(bitxr[i-1]);
        int p=add_and({xorx[i-1],q});
        ansbitx[i]=add_xor({ansbitx[i],p});
    } //for (auto x:ansbitx) cout<<x<<' '; cout<<'\n';
    for (int i=1; (1<<i)<w; ++i) {
        int q=add_not(bityr[i-1]);
        int p=add_and({ansbity[i-1],q});
        ansbity[i]=add_xor({xory[i],p});
    } //for (auto x:ansbity) cout<<x<<' '; cout<<'\n';

    vector<int> xorans(10,zero);
    for (int i=0; i<10; ++i) xorans[i]=add_xor({ansbity[i],ansbitx[i]});

    ansbit[0]=xorans[0];
    for (int i=1; i<10; ++i) {
        int p=add_and({ansbitx[i-1],ansbity[i-1]});
        int q=add_or({ansbitx[i-1],ansbity[i-1]});
        int t=add_xor({q,ansbit[i-1]});
        int z=add_and({t,q});
        int o=add_or({p,z});
        ansbit[i]=add_xor({xorans[i],o});
    }   

    vector<int> forans;
    for (int i=0; i<10; ++i) {

        if (k&(1<<i)) forans.push_back(ansbit[i]);
        else {
            int v=add_not(ansbit[i]);
            forans.push_back(v);
        }

    }
    int ans=add_and(forans);
    add_or({ans,inSameCol,inSameRow});

}

Compilation message (stderr)

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:14:9: warning: unused variable 'one' [-Wunused-variable]
   14 |     int one = add_not(zero);
      |         ^~~

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