Submission #485863

#	Time	Username	Problem	Language	Result	Execution time	Memory
485863		ljuba	Vision Program (IOI19_vision)	C++17	100 / 100	56 ms	6212 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
 
using namespace std;
 
map<int, vector<int>> leva, desna;
map<int, int> ksorLeva, ksorDesna;
map<int, int> orLeva, orDesna;
 
int izracunajLevo(int K) {
    vector<int> pitaj;
 
    for(auto z : leva) {
        int ksor = ksorLeva[z.first];
        int ili = orLeva[z.first];
        ksor = add_not(ksor);
        pitaj.push_back(add_and({ksor, ili}));
    }
 
    for(auto z : leva) {
        int prvi = z.first;
        int drugi = z.first+K;
        if(!leva.count(drugi))
            continue;
        vector<int> zaOr, zaXor;
        for(int i = prvi; i <= drugi; ++i) {
            zaOr.push_back(orLeva[i]);
            zaXor.push_back(ksorLeva[i]);
        }
        prvi = add_or(zaOr);
        drugi = add_not(add_xor(zaXor));
        pitaj.push_back(add_and({prvi, drugi}));
    }
 
    return add_or(pitaj);
}
 
int izracunajDesno(int K) {
    vector<int> pitaj;
 
    for(auto z : desna) {
        int ksor = ksorDesna[z.first];
        int ili = orDesna[z.first];
        ksor = add_not(ksor);
        pitaj.push_back(add_and({ksor, ili}));
    }
 
    for(auto z : desna) {
        int prvi = z.first;
        int drugi = z.first+K;
        if(!desna.count(drugi))
            continue;
        vector<int> zaOr, zaXor;
        for(int i = prvi; i <= drugi; ++i) {
            zaOr.push_back(orDesna[i]);
            zaXor.push_back(ksorDesna[i]);
        }
        prvi = add_or(zaOr);
        drugi = add_not(add_xor(zaXor));
        pitaj.push_back(add_and({prvi, drugi}));
    }
 
    return add_or(pitaj);
 
}
 
int calc(int K) {
    int prvi = izracunajLevo(K);
    int drugi = izracunajDesno(K);
    return add_and({prvi, drugi});
}
 
void construct_network(int H, int W, int K) {
    for(int i = 0; i < H; ++i) {
        for(int j = 0; j < W; ++j) {
            int trenutni = i*W + j;
            desna[i-j].push_back(trenutni);
            leva[i+j].push_back(trenutni);
        }
    }
 
    for(auto z : leva) {
        ksorLeva[z.first] = add_xor(z.second);
        orLeva[z.first] = add_or(z.second);
    }
 
    for(auto z : desna) {
        ksorDesna[z.first] = add_xor(z.second);
        orDesna[z.first] = add_or(z.second);
    }

    if(K == 1) {
        calc(1);
        return;
    }
 
    int prvi = K-1, drugi = K;
    prvi = calc(prvi), drugi = calc(drugi);
    add_xor({prvi, drugi});
}

• 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