Submission #390680

#	Time	Username	Problem	Language	Result	Execution time	Memory
390680		benedict0724	Vision Program (IOI19_vision)	C++17	0 / 100	1 ms	588 KiB

vision

#include "vision.h"

using namespace std;
void construct_network(int H, int W, int K) {
	vector<int> Ns, garo, sero, gbesu, sbesu, gd, sd, prime;
//H * W ~ (H + 1) * W - 1 : 가로줄
	for(int i=0;i<H;i++)
    {
        Ns.clear();
        for(int j=0;j<W;j++) Ns.push_back(W * i + j);
        garo.push_back(add_or(Ns));
    }
//H * W + W ~ H * W + W + H - 1 : 세로줄
    for(int j=0;j<W;j++)
    {
        Ns.clear();
        for(int i=0;i<H;i++) Ns.push_back(W * i + j);
        sero.push_back(add_or(Ns));
    }
    gbesu.push_back(0);
    sbesu.push_back(0);
    for(int i=1;i<=min(H-1, K);i++)
    {
        int x = i;
        for(int j=2;j<x;j++)
        {
            if(x%j == 0){
                while(x%j == 0) x /= j;
                break;
            }
        }
        if(x != 1)
        {
            gbesu.push_back(0);
            continue;
        }
        vector<int> tmp;
        for(int j=0;j<i;j++)
        {
            vector<int> mod;
            for(int k=j;k<H;k+=i)
                mod.push_back(k);
            if(mod.size() <= 1) continue;
            int p = add_xor(mod);
            int q = add_or(mod);

            vector<int> t = {p, q};
            tmp.push_back(add_xor(t));
        }
        gbesu.push_back(add_or(tmp));
    }

    for(int i=1;i<=min(W-1, K);i++)
    {
        int x = i;
        for(int j=2;j<x;j++)
        {
            if(x%j == 0){
                while(x%j == 0) x /= j;
                break;
            }
        }
        if(x != 1)
        {
            sbesu.push_back(0);
            continue;
        }
        vector<int> tmp;
        for(int j=0;j<i;j++)
        {
            vector<int> mod;
            for(int k=j;k<W;k+=i)
                mod.push_back(k);
            if(mod.size() <= 1) continue;
            int p = add_xor(mod);
            int q = add_or(mod);

            vector<int> t = {p, q};
            tmp.push_back(add_xor(t));
        }
        sbesu.push_back(add_or(tmp));
    }

    for(int i=2;i<=200;i++)
    {
        int cnt = 0;
        for(int j=2;j<i;j++) if(i%j == 0) cnt++;
        if(cnt == 0) prime.push_back(i);
    }

    gd.push_back(add_not(gbesu[1]));
    gd.push_back(gbesu[1]);
    sd.push_back(add_not(sbesu[1]));
    sd.push_back(sbesu[1]);

    for(int i=2;i<=H-1;i++)
    {
        int x = i;
        vector<int> tmp;
        for(int p : prime)
        {
            if(p * i > H-1) break;
            int now = 1;
            while(x % p == 0)
            {
                now *= p;
                x /= p;
            }

            if(now * p > H-1) tmp.push_back(gbesu[now]);
            else{
                vector<int> t = {gbesu[now], gbesu[now * p]};
                tmp.push_back(add_xor(t));
            }
        }

        gd.push_back(add_and(tmp));
    }

    for(int i=2;i<=W-1;i++)
    {
        int x = i;
        vector<int> tmp;
        for(int p : prime)
        {
            if(p * i > H-1) break;
            int now = 1;
            while(x % p == 0)
            {
                now *= p;
                x /= p;
            }

            if(now * p > H-1) tmp.push_back(sbesu[now]);
            else{
                vector<int> t = {sbesu[now], sbesu[now * p]};
                tmp.push_back(add_xor(t));
            }
        }

        sd.push_back(add_and(tmp));
    }

    vector<int> fin;
    for(int i=0;i<=min(H-1, K);i++)
    {
        if(K - i >= 0)
        {
            vector<int> t = {gd[i], sd[K-i]};
            fin.push_back(add_and(t));
        }
    }

    add_or(fin);
}

• 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