Submission #1165301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165301		AlgorithmWarrior	Vision Program (IOI19_vision)	C++20	100 / 100	9 ms	1728 KiB

vision

#include <bits/stdc++.h>
#include "vision.h"

using namespace std;

int ind(int lin,int col,int W){
    return lin*W+col;
}

vector<int>coord(int l1,int l2,int c1,int c2,int W){
    vector<int>coor;
    int i,j;
    for(i=l1;i<=l2;++i)
        for(j=c1;j<=c2;++j)
            coor.push_back(ind(i,j,W));
    return coor;
}

int nrbiti(int x){
    int nrb=0;
    while(x){
        x/=2;
        ++nrb;
    }
    return nrb;
}

int pos_unu;
int pos_zero;

vector<int>upgrade(vector<int>oldcount,int nr,int add){
    int nrb=nrbiti(nr);
    vector<int>pref;
    vector<int>change;
    vector<int>counter;
    pref.push_back(pos_unu);
    int i;
    for(i=1;i<nrb;++i)
        pref.push_back(add_and({pref[i-1],oldcount[i-1]}));
    for(i=0;i<nrb;++i)
        change.push_back(add_and({add,pref[i]}));
    if(!(nr&(nr-1)))
        oldcount.push_back(pos_zero);
    for(i=0;i<nrb;++i)
        counter.push_back(add_xor({oldcount[i],change[i]}));
    return counter;
}

void construct_network(int H, int W, int K) {
    vector<int>interes;
    int i;
    interes.push_back(add_xor(coord(0,0,0,W-1,W)));
    for(i=1;i<H;++i){
        vector<int>ask=coord(i,i,0,W-1,W);
        ask.push_back(interes.back());
        interes.push_back(add_xor(ask));
    }
    interes.push_back(add_xor(coord(0,H-1,0,0,W)));
    for(i=1;i<W;++i){
        vector<int>ask=coord(0,H-1,i,i,W);
        ask.push_back(interes.back());
        interes.push_back(add_xor(ask));
    }
    pos_unu=add_or(interes);
    pos_zero=add_and(interes);
    vector<int>counter;
    counter.push_back(interes[0]);
    for(i=1;i<H+W;++i)
        counter=upgrade(counter,i+1,interes[i]);
    int nrb=nrbiti(H+W);
    for(i=0;i<nrb;++i)
        if(!(K&(1<<i)))
            counter[i]=add_not(counter[i]);
    add_and(counter);
}

• 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