Submission #615962

#	Time	Username	Problem	Language	Result	Execution time	Memory
615962		neki	Vision Program (IOI19_vision)	C++14	100 / 100	97 ms	10860 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
#define vc vector
#define ll int
#define loop(i, a, b) for(ll i=a;i<b;++i)

using namespace std;

/*vc<ll> zac={1, 0, 0, 0,    
            0, 0, 0, 0,    
            0, 0, 0, 1};

void add_and(vc<ll> a){zac.push_back(1); for(auto v: a) assert(v<zac.size()), zac[zac.size()-1]&=zac[v];};
void add_or(vc<ll> a ){zac.push_back(0); for(auto v: a) assert(v<zac.size()), zac[zac.size()-1]|=zac[v];};
void add_xor(vc<ll> a){zac.push_back(0); for(auto v: a) assert(v<zac.size()), zac[zac.size()-1]^=zac[v];};
void add_not(ll a){assert(a<zac.size()), zac.push_back(!zac[a]);};*/

void construct_network(int h, int w, int k){
    ll cur=h * w;
    function<ll (ll)> less=[&](ll d){
        function<ll (vc<vc<ll>>)> preglejdiag=[&](vc<vc<ll>> kje){
            
            vc<ll> dor, dxor;
            for(ll i=0;i<h+w-1;++i){
                vc<ll> que;
                for(ll x=i, y=0;x>=0;--x, ++y) if(x<h and y<w){
                    
                    que.push_back(kje[x][y]);
                    //cout << kje[x][y] << endl;
                }
                //cout << endl;
                dor.push_back(cur++);add_or(que);
                //cout << zac[dor[i]]<<" ";
                dxor.push_back(cur++);add_xor(que);
            }
            //cout << endl;
            //for(auto v: dor) cout << zac[v] << " ";cout << endl;
            
            vc<ll> blor, blxor;
            for(ll i=0;i<h+w-1;++i){
                vc<ll> que;
                for(ll j=i;j<h+w-1 and j<=i+d;++j) que.push_back(dor[j]);
                blor.push_back(cur++);add_or(que);
            }
            for(ll i=0;i<h+w-1;++i){
                vc<ll> que;
                for(ll j=i;j<h+w-1 and j<=i+d;++j) que.push_back(dxor[j]);
                ll temp=cur++; add_xor(que);
                blxor.push_back(cur++);add_not(temp);
            }
            assert(blor.size()==blxor.size());
            
            vc<ll> vand;
            for(ll i=0;i<blor.size();++i) vand.push_back(cur++), add_and({blor[i], blxor[i]});
        
            add_or(vand);
            
            return cur++;
        };
        vc<vc<ll>> pkje(h, vc<ll>(w)), nkje(h, vc<ll>(w));
        for(ll i=0, cnt=0;i<h;++i) for(ll j=0;j<w;++j) pkje[i][j]=cnt++;
        for(ll i=h-1, cnt=0;i>=0;--i) for(ll j=0;j<w;++j) nkje[i][j]=cnt++;
        
        add_and({preglejdiag(pkje), preglejdiag(nkje)});
        return cur++;
    };
    
    if(k==1) less(1);
    else{
        ll manj=less(k-1);
        add_not(manj);ll nmanj=cur++;
        ll temp=less(k);
        
        //cout << zac[manj] << " "<< zac[temp] << endl;
        
        
        add_and({nmanj, temp});
    }
}

Compilation message (stderr)

vision.cpp: In lambda function:
vision.cpp:54:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for(ll i=0;i<blor.size();++i) vand.push_back(cur++), add_and({blor[i], blxor[i]});
      |                        ~^~~~~~~~~~~~

• 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