Submission #943456

#	Time	Username	Problem	Language	Result	Execution time	Memory
943456		djs100201	Vision Program (IOI19_vision)	C++17	100 / 100	25 ms	5240 KiB

vision

#include<bits/stdc++.h>
#include "vision.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ =2024+100, inf = (ll)2e9 * (ll)1e9 + 7, mod = 998244353;
ll n, m, tc = 1, a, b, c, d, sum, x, y, z, base, ans, k;
ll gcd(ll x,ll y){
	if(!y)return x;
	return gcd(y,x%y);
}
int idx[n_][n_];
void construct_network(int H, int W, int K) {
	vector<int> Ns;
    for(int i=0;i<H;i++)
        for(int j=0;j<W;j++)idx[i][j]=base++;
    //0 1 2 3 .. W-1
    //
    vector<int>N(H),M(W);
    for(int i=0;i<H;i++){
        N[i]=base++;
        for(int j=0;j<W;j++)Ns.push_back(W*i+j);
        add_or(Ns);
        Ns.clear();
    }
    for(int i=0;i<W;i++){
        M[i]=base++;
        for(int j=0;j<H;j++)Ns.push_back(idx[j][i]);
        add_or(Ns);
        Ns.clear();
    }
    vector<int>N2(9,-1),M2(9,-1),C(9,-1),res(9,-1);
    for(int i=0;i<9;i++){
        a=(1ll<<i);
        vector<int>T;
        for(int j=0;j+a<H;j++){
            vector<int>T2;
            for(int k=j+a;k<H;k++){
                int dif=k-j;
                if(dif&a){
                    T2.push_back(N[k]);
                }
            }
            if(T2.empty())continue;
            int x=base++;
            add_or(T2);
            Ns={N[j],x};
            T.push_back(base++);
            add_and(Ns);
            Ns.clear();
        }
        if(T.empty())continue;
        N2[i]=base++;
        add_or(T);
    }
    for(int i=0;i<9;i++){
        a=(1ll<<i);
        vector<int>T;
        for(int j=0;j+a<W;j++){
            vector<int>T2;
            for(int k=j+a;k<W;k++){
                int dif=k-j;
                if(dif&a)T2.push_back(M[k]);
            }
            int x=base++;
            add_or(T2);
            Ns={M[j],x};
            T.push_back(base++);
            add_and(Ns);
            Ns.clear();
        }
        if(T.empty())continue;
        M2[i]=base++;
        add_or(T);
    }
    if(H>=2 && W>=2){
        res[0]=base++;
        add_xor({N2[0],M2[0]});
        C[1]=base++;
        add_and({N2[0],M2[0]});
        for(int i=1;i<9;i++){
            if(N2[i]==-1 && M2[i]==-1){
                res[i]=C[i];
                break;
            }
            if(N2[i]==-1){
                res[i]=base++;
                add_xor({M2[i],C[i]});
                C[i+1]=base++;
                add_and({M2[i],C[i]});
            }
            else if(M2[i]==-1){
                res[i]=base++;
                add_xor({N2[i],C[i]});
                C[i+1]=base++;
                add_and({N2[i],C[i]});
            }
            else{
                res[i]=base++;
                add_xor({N2[i],M2[i],C[i]});
                a=base++;
                add_and({N2[i],C[i]});
                b=base++;
                add_and({M2[i],C[i]});
                c=base++;
                add_and({N2[i],M2[i]});
                C[i+1]=base++;
                add_or({(int)a,(int)b,(int)c});
            }
        }
    }
    else if(H==1){
        for(int i=0;i<9;i++){
            res[i]=M2[i];
        }
    }
    else if(W==1){
        for(int i=0;i<9;i++){
            res[i]=N2[i];
        }
    }
    vector<int>fin;
    for(int i=0;i<9;i++){
        if(res[i]==-1)continue;
        //cout<<i<<' '<<res[i]<<' '<<B[res[i]]<<endl;
        a=(1<<i);
        if(!(K&a)){
            add_not(res[i]);
            res[i]=base++;
        }
        fin.push_back(res[i]);
    }
    add_and(fin);
    //cout<<res[0]<<' '<<B[res[0]]<<endl; 
 
}

• 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