제출 #415598

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415598		qwerasdfzxcl	Vision Program (IOI19_vision)	C++14	0 / 100	7 ms	1440 KiB

vision

#include <bits/stdc++.h>
#include "vision.h"

typedef long long ll;
using namespace std;
vector<int> p;
int factor[202];
bool prime[202];

void getprime(){
    fill(prime+2, prime+202, 1);
    for (int i=2;i<202;i++) if (prime[i]){
        p.push_back(i);
        for (int j=2;i*j<202;j++) prime[i*j] = 1;
    }
}

void factorize(int n){
    fill(factor, factor+202, 0);
    for (auto &x:p){
        while(n%x==0){
            factor[x]++;
            n /= x;
        }
    }
}

void construct_network(int n, int m, int k) {
    getprime();
    vector<int> row;
    for (int i=0;i<n;i++){
        vector<int> tmp;
        for (int j=0;j<m;j++) tmp.push_back(i*m+j);
        row.push_back(add_or(tmp));
    }
    int row_pos0 = add_xor(row);
    vector<vector<int>> row_pk;
    row_pk.resize(n);
    for (int i=0;i<n;i++){
        row_pk[i].push_back(-1);
        if (!prime[i]) continue;
        for (int cur=i;cur<n;cur*=i){
            vector<int> tmp2;
            for (int t=0;t<cur;t++){
                vector<int> tmp;
                for (int j=0;t+i*j<n;j++) tmp.push_back(row[t+i*j]);
                if (tmp.size()==1){
                    tmp2.push_back(tmp[0]);
                    continue;
                }
                tmp2.push_back(add_xor(tmp));
            }
            row_pk[i].push_back(add_not(add_or(tmp2)));
            add_not(row_pk[i].back());
        }
    }
    row_pk[0][0] = row_pos0;
    vector<int> tmpv_row;
    tmpv_row.push_back(row_pos0);
    for (int i=2;i<n;i++){
        factorize(i);
        vector<int> tmp;
        for (auto &x:p){
            if (factor[x]) tmp.push_back(row_pk[x][factor[x]]);
            if (factor[x]<(int)row_pk[x].size()-1) tmp.push_back(row_pk[x][factor[x]+1]+1);
        }
        row_pk[i][0] = add_and(tmp);
        tmpv_row.push_back(row_pk[i][0]);
    }
    row_pk[1][0] = add_not(add_or(tmpv_row));

    vector<int> col;
    for (int j=0;j<m;j++){
        vector<int> tmp;
        for (int i=0;i<n;i++) tmp.push_back(i*m+j);
        col.push_back(add_or(tmp));
    }
    int col_pos0 = add_xor(col);
    vector<vector<int>> col_pk;
    col_pk.resize(m);
    for (int j=0;j<m;j++){
        col_pk[j].push_back(-1);
        if (!prime[j]) continue;
        for (int cur=j;cur<m;cur*=j){
            vector<int> tmp2;
            for (int t=0;t<cur;t++){
                vector<int> tmp;
                for (int i=0;t+i*j<m;i++) tmp.push_back(col[t+i*j]);
                if (tmp.size()==1){
                    tmp2.push_back(tmp[0]);
                    continue;
                }
                tmp2.push_back(add_xor(tmp));
            }
            col_pk[j].push_back(add_not(add_or(tmp2)));
            add_not(col_pk[j].back());
        }
    }
    col_pk[0][0] = col_pos0;
    vector<int> tmpv_col;
    tmpv_col.push_back(col_pos0);
    for (int j=2;j<m;j++){
        factorize(j);
        vector<int> tmp;
        for (auto &x:p){
            if (x>=m) break;
            if (factor[x]) tmp.push_back(col_pk[x][factor[x]]);
            if (factor[x]<(int)col_pk[x].size()-1) tmp.push_back(col_pk[x][factor[x]+1]+1);
        }
        col_pk[j][0] = add_and(tmp);
        tmpv_col.push_back(col_pk[j][0]);
    }
    col_pk[1][0] = add_not(add_or(tmpv_col));


    vector<int> ans;
    for (int i=0;i<=k;i++){
        if (i>=n || k-i>=m) continue;
        vector<int> tmp;
        tmp.push_back(row_pk[i][0]);
        tmp.push_back(col_pk[k-i][0]);
        ans.push_back(add_and(tmp));
    }
    add_or(ans);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 15
• Subtask 5: 0 / 12
• Subtask 6: 0 / 8
• Subtask 7: 0 / 14
• Subtask 8: 0 / 19