Submission #293803

#	Time	Username	Problem	Language	Result	Execution time	Memory
293803		tqbfjotld	Vision Program (IOI19_vision)	C++14	100 / 100	16 ms	2048 KiB

vision

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

vector<int> diag1[405],diag2[405];
int orloc1[405],orloc2[405];
int ddiag1[405],ddiag2[405];
int prefor1[405],prefor2[405],sufor1[405],sufor2[405];

void construct_network(int H, int W, int K) {
    int c = 0;
    for (int x = 0; x<H; x++){
        for (int y = 0; y<W; y++){
            diag1[x+y].push_back(c);
            diag2[x-y-1+W].push_back(c);
            c++;
        }
    }
    for (int x = 0; x<H+W-1; x++){
        /*printf("diag 2: ");
        for (auto y : diag2[x]){
            printf("%d ",y);
        }
        printf("\n");*/
        orloc1[x] = add_or(diag1[x]);
        orloc2[x] = add_or(diag2[x]);
    }
    for (int x = 0; x+K<H+W-1; x++){
        vector<int> qu = {orloc1[x],orloc1[x+K]};
        ddiag1[x] = add_and(qu);
        qu = {orloc2[x],orloc2[x+K]};
        ddiag2[x] = add_and(qu);
    }
    prefor1[0] = orloc1[0];
    prefor2[0] = orloc2[0];
    for (int x = 1; x<H+W-1; x++){
        vector<int> qu = {prefor1[x-1],orloc1[x]};
        prefor1[x] = add_or(qu);
        qu = {prefor2[x-1],orloc2[x]};
        prefor2[x] = add_or(qu);
    }
    sufor1[H+W-2] = orloc1[H+W-2];
    sufor2[H+W-2] = orloc2[H+W-2];
    for (int x = H+W-3; x>=0; x--){
        vector<int> qu = {sufor1[x+1],orloc1[x]};
        sufor1[x] = add_or(qu);
        qu = {sufor2[x+1],orloc2[x]};
        sufor2[x] = add_or(qu);
    }
    int someres1,someres2;
    vector<int> q;
    for (int x = 0; x+K<H+W-1; x++){
        q.push_back(ddiag1[x]);
    }
    someres1 = add_or(q);
    q.clear();
    for (int x = 0; x+K<H+W-1; x++){
        q.push_back(ddiag2[x]);
    }
    someres2 = add_or(q);
    if (K==H+W-2){
        add_or({someres1,someres2});
    }
    else{
        int more1,more2;
        vector<int> qu = {prefor1[0],sufor1[K+1]};
        more1 = add_and(qu);
        qu = {prefor2[0],sufor2[K+1]};
        more2 = add_and(qu);
        for (int x = 1; x+K+1<H+W-1; x++){
            qu = {prefor1[x],sufor1[x+K+1]};
            int res1 = add_and(qu);
            more1 = add_or({more1,res1});
            int res2 = add_and({prefor2[x],sufor2[x+K+1]});
            more2 = add_or({res2,more2});
        }
        more1 = add_not(more1);
        more2 = add_not(more2);
        int otherres1 = add_and({someres1,more2});
        int otherres2 = add_and({someres2,more1});
        add_or({otherres1,otherres2});
    }

}

• 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