Submission #585405

#	Time	Username	Problem	Language	Result	Execution time	Memory
585405		Valters07	Vision Program (IOI19_vision)	C++14	100 / 100	10 ms	1876 KiB

vision

#include <bits/stdc++.h>
#include "vision.h"
#pragma GCC optimize("O2,unroll-loops")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define en cin.close();return 0;
#define pb push_back
#define fi first//printf("%lli\n",cur);
#define se second//scanf("%lli",&n);
#define r0 return 0;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int check_if_less_than_k(int h, int w, int diagc, int k, vector<int> &vd1, vector<int> &vd2)
{
    vector<int> xve1(diagc), xve2(diagc), ve;
    for(int i = 0;i<diagc;i++)
    {
        vector<int> tmp = {vd1[i]};
        if(i>0)
            tmp.pb(xve1[i-1]);
        xve1[i]=add_xor(tmp);
    }
    for(int i = k;i<diagc;i++)
        ve.pb(add_and({xve1[i-k],xve1[i]}));
    int p1 = add_not(add_and({add_not(xve1.back()),add_or(ve)}));
    ve.clear();
    for(int i = 0;i<diagc;i++)
    {
        vector<int> tmp = {vd2[i]};
        if(i>0)
            tmp.pb(xve2[i-1]);
        xve2[i]=add_xor(tmp);
    }
    for(int i = k;i<diagc;i++)
        ve.pb(add_and({xve2[i-k],xve2[i]}));
    int p2 = add_not(add_and({add_not(xve2.back()),add_or(ve)}));
    return add_and({p1,p2});
}
void construct_network(int h, int w, int k)
{
    int diagc = h+w-1;
    vector<int> d1[diagc], d2[diagc];
    for(int i = 0;i<h;i++)
        for(int j = 0;j<w;j++)
            d1[i+j].pb(i*w+j),
            d2[i-j+(w-1)].pb(i*w+j);
    vector<int> vd1(diagc), vd2(diagc);
    for(int i = 0;i<diagc;i++)
        vd1[i]=add_or(d1[i]);
    for(int i = 0;i<diagc;i++)
        vd2[i]=add_or(d2[i]);
    int p1 = check_if_less_than_k(h,w,diagc,k,vd1,vd2);
    if(k==1)
        return;
    int p2 = check_if_less_than_k(h,w,diagc,k-1,vd1,vd2);
    p2=add_not(p2);
    add_and({p1,p2});
    return;
}

• 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