제출 #720445

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720445		bin9638	Vision Program (IOI19_vision)	C++17	100 / 100	18 ms	1820 KiB

vision

#include <bits/stdc++.h>

#ifndef SKY
#include "vision.h"
#endif // SKY

using namespace std;

#define N 210
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back

const int num_bit=9;

#ifdef SKY
vector<int>ask;

int add_not(int x)
{
    int res=ask.size();
    ask.pb((!ask[x]));
    return res;
}

int add_and(vector<int>s)
{
    assert(!s.empty());
    int res=ask.size();
    int val=1;
    for(auto u:s)
        val&=ask[u];
    ask.pb(val);
    return res;
}

int add_or(vector<int>s)
{
     assert(!s.empty());
    int res=ask.size();
    int val=0;
    for(auto u:s)
        val|=ask[u];
    ask.pb(val);
    return res;
}

int add_xor(vector<int>s)
{
     assert(!s.empty());
    int res=ask.size();
    int val=0;
    for(auto u:s)
        val^=ask[u];
    ask.pb(val);
    return res;
}
#endif // SKY

int bit_0,bit_1;

int solve(int pos,int x,int vt)
{
    vector<int>them;
    for(int i=0;i<vt;i++)
        them.pb(bit_0);
    them.pb(x);
    for(int i=vt+1;i<num_bit;i++)
        them.pb(add_and({them[i-1],pos+i-1}));
    int res=add_xor({them[0],pos});
    for(int i=1;i<num_bit;i++)
        add_xor({them[i],pos+i});
    return res;
}

int build(int n,vector<int>s,int id)
{
    //cout<<n<<endl;
    //for(auto u:s)cout<<ask[u]<<" ";cout<<endl;
    vector<int>hoi;
    for(auto u:s)
        hoi.pb(u);
    int kt=add_xor(hoi),copy_kt=kt;
    kt=add_not(kt);
    bit_0=add_and({kt,copy_kt});
    for(int i=0;i<n;i++)
        s[i]=add_and({s[i],kt});
    for(int i=1;i<n;i++)
    s[i]=add_xor({s[i],s[i-1]});
   // for(auto u:s)cout<<ask[u]<<" ";cout<<endl;
    int pos=add_and({bit_0});
    for(int i=1;i<num_bit;i++)
        add_and({bit_0});
    for(int i=0;i<n;i++)
        pos=solve(pos,s[i],0);
    //for(int i=0;i<num_bit;i++)cout<<ask[pos+i]<<" ";cout<<endl;
    return pos;
}

void construct_network(int n, int m, int k)
{
    vector<int>s;
    int pos[2];
    //hàng
    for(int i=0;i<n;i++)
    {
        vector<int>hoi;
        for(int j=0;j<m;j++)
            hoi.pb(i*m+j);
        s.pb(add_or(hoi));
    }
    pos[0]=build(n,s,0);
    //cột
    s.clear();
    for(int j=0;j<m;j++)
    {
        vector<int>hoi;
        for(int i=0;i<n;i++)
            hoi.pb(i*m+j);
        s.pb(add_or(hoi));
    }
    pos[1]=build(m,s,1);
   // cout<<pos[0]<<" "<<pos[1]<<endl;
   bit_1=add_not(bit_0);
   int vt=pos[0];
   for(int i=0;i<num_bit;i++)
        vt=solve(vt,pos[1]+i,i);
   //for(int i=0;i<num_bit;i++)cout<<ask[vt+i]<<" ";cout<<endl;
    int pos_k=add_and({(k%2==1 ? bit_1 : bit_0)});
    for(int i=1;i<num_bit;i++)
       add_and({((k>>i)&1) ? bit_1 : bit_0});
    vector<int>hoi;
    for(int i=0;i<num_bit;i++)
        hoi.pb(add_xor({vt+i,pos_k+i}));
    add_not(add_or(hoi));
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            int u;
            cin>>u;
            ask.pb(u);
        }
    construct_network(n,m,k);
    cout<<ask.back();
    return 0;
}
#endif

• 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