Submission #973802

#	Time	Username	Problem	Language	Result	Execution time	Memory
973802		hirayuu_oj	Vision Program (IOI19_vision)	C++17	100 / 100	21 ms	3420 KiB

vision

#include "vision.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(),x.end()
using ll=long long;

int h,w,k;

int pos(int i,int j){
    return i*w+j;
}
int ind(int i){
    return h*w+i;
}

void construct_network(int H, int W, int K) {
    h=H;
    w=W;
    k=K;
    vector<vector<int>> plus(H+W-1);
    rep(i,H){
        rep(j,W){
            plus[i+j].push_back(pos(i,j));
        }
    }
    vector<vector<int>> minus(H+W-1);
    rep(i,H){
        rep(j,W){
            minus[i+(W-j-1)].push_back(pos(i,j));
        }
    }
    int cnt=0;
    vector<int> plus_pos,minus_pos;
    rep(i,H+W-1){
        add_or(plus[i]);
        plus_pos.push_back(ind(cnt));
        cnt++;
    }
    rep(i,H+W-1){
        add_or(minus[i]);
        minus_pos.push_back(ind(cnt));
        cnt++;
    }
    vector<int> wide;
    add_xor(plus_pos);
    wide.push_back(ind(cnt));
    cnt++;
    rep(i,H+W-1-K){
        vector<int> now;
        rep(j,K+1){
            now.push_back(plus_pos[i+j]);
        }
        add_or(now);
        cnt++;
        add_xor(now);
        cnt++;
        add_not(ind(cnt-1));
        cnt++;
        add_and({ind(cnt-3),ind(cnt-1)});
        wide.push_back(ind(cnt));
        cnt++;
    }
    add_or(wide);
    int wp=ind(cnt);
    cnt++;
    wide.clear();
    add_xor(minus_pos);
    wide.push_back(ind(cnt));
    cnt++;
    rep(i,H+W-1-K){
        vector<int> now;
        rep(j,K+1){
            now.push_back(minus_pos[i+j]);
        }
        add_or(now);
        cnt++;
        add_xor(now);
        cnt++;
        add_not(ind(cnt-1));
        cnt++;
        add_and({ind(cnt-3),ind(cnt-1)});
        wide.push_back(ind(cnt));
        cnt++;
    }
    add_or(wide);
    int wm=ind(cnt);
    cnt++;
    add_and({wp,wm});
    int wide_ok=ind(cnt);
    cnt++;
    vector<int> just;
    rep(i,H+W-1-K){
        vector<int> now;
        rep(j,K+1){
            now.push_back(plus_pos[i+j]);
        }
        add_and({now[0],now.back()});
        just.push_back(ind(cnt));
        cnt++;
    }
    rep(i,H+W-1-K){
        vector<int> now;
        rep(j,K+1){
            now.push_back(minus_pos[i+j]);
        }
        add_and({now[0],now.back()});
        just.push_back(ind(cnt));
        cnt++;
    }
    add_or(just);
    int jp=ind(cnt);
    cnt++;
    add_and({wide_ok,jp});
}

• 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