제출 #573062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
573062		MadokaMagicaFan	Vision Program (IOI19_vision)	C++14	100 / 100	19 ms	1744 KiB

vision

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define all(v)                      v.begin(), v.end()
#define rall(v)                     v.rbegin(), v.rend()
#define sz(v)                       ((int)v.size())

#define forn(i,n)                   for(int i = 0; i < n; ++i)
#define forbe(i,b,e)                for(int i = b; i < e; ++i)

#define pb                          push_back

#define pry                         puts("YES")
#define prn                         puts("NO")
#define endl                        '\n'

#define fst                         first
#define scn                         second

const int K = 10;

int add_not(int N);
int add_and(vector<int> s);
int add_or(vector<int> s);
int add_xor(vector<int> s);

#ifdef ONPC
int cnt1, cnt2;

vector<int> table;


int 
add_not(int N)
{
    ++cnt1;
    ++cnt2;
    assert(N<sz(table));
    if (table[N])
        table.pb(0);
    else
        table.pb(1);
    return sz(table)-1;
}

int
add_and(vector<int> s)
{
    int ans = 0;
    ++cnt1;
    cnt2 += sz(s);
    for (int i = 0; i < sz(s); ++i)
        assert(s[i] < sz(table));
    for (int i = 0; i < sz(s); ++i)
        ans += table[s[i]];
    if (ans==sz(s))
        table.pb(1);
    else
        table.pb(0);
    return sz(table)-1;
}

int
add_or(vector<int> s)
{
    int ans = 0;
    ++cnt1;
    cnt2 += sz(s);
    for (int i = 0; i < sz(s); ++i)
        assert(s[i] < sz(table));
    for (int i = 0; i < sz(s); ++i)
        ans += table[s[i]];
    if (ans>0)
        table.pb(1);
    else
        table.pb(0);
    return sz(table)-1;
}

int
add_xor(vector<int> s)
{
    int ans = 0;
    ++cnt1;
    cnt2 += sz(s);
    for (int i = 0; i < sz(s); ++i)
        assert(s[i] < sz(table));
    for (int i = 0; i < sz(s); ++i)
        ans += table[s[i]];
    if (ans&1)
        table.pb(1);
    else
        table.pb(0);
    return sz(table)-1;
}
#endif

void
construct_network(int h, int w, int k)
{
    vector<int> rowOR(h);
    vector<int> colOR(w);
    vector<int> bitx(K);
    vector<int> bity(K);
    vector<int> bitans(K);
    int zero;
    int z = 0;
    int u1,u2,u3,u4;

    vector<int> q;
    vector<int> lastq;
    vector<int> bigq;

    q.resize(w);
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            q[j] = i * w + j;
        }
        rowOR[i] = add_xor(q);
    }

    q.resize(h);
    for (int i = 0; i < w; ++i) {
        for (int j = 0; j < h; ++j) {
            q[j] = j * w + i;
        }
        colOR[i] = add_xor(q);
    }

    if (w * h > 2)
        zero = add_and({0,1,2});
    else
        zero = add_not(0);

    for (int i = 0; i < K; ++i) {
        bitx[i] = zero;
        bity[i] = zero;
    }

    /* Get y height */
    q.clear();
    for (int i = 0; i < h; ++i) {
        q.pb(rowOR[i]);
        bigq.pb(add_xor(q));
    }
    z = 0;
    while (1) {
        assert(z<10);
        q = bigq;
        /* cout << "y " << z << ": "; */
        /* for (int u : q) */
        /*     cout << table[u]; */
        /* cout << endl; */
        bity[z] = add_xor(q);
        if (q.size() == 1)
            break;
        bigq.clear();
        for (int i = 0; i < sz(q)-1; i+=2) {
            u1 = add_and({q[i],q[i+1]});
            u2 = add_xor({q[i],q[i+1],bity[z]});
            u3 = add_and({u2,q[i+1]});
            bigq.pb(add_or({u1,u3}));
        }
        ++z;
    }

    /* Get x height */
    q.clear();
    bigq.clear();
    for (int i = 0; i < w; ++i) {
        q.pb(colOR[i]);
        bigq.pb(add_xor(q));
    }
    z = 0;
    while (1) {
        assert(z<10);
        q = bigq;
        /* cout << "x " << z << ": "; */
        /* for (int u : q) */
        /*     cout << table[u]; */
        /* cout << endl; */
        bitx[z] = add_xor(q);
        if (q.size() == 1)
            break;
        bigq.clear();
        for (int i = 0; i < sz(q)-1; i+=2) {
            u1 = add_and({q[i],q[i+1]});
            u2 = add_xor({q[i],q[i+1],bitx[z]});
            u3 = add_and({u2,q[i+1]});
            bigq.pb(add_or({u1,u3}));
        }
        ++z;
    }

    /* for (int i = K-1; i >= 0; --i) cout << table[bitx[i]]; */
    /* cout << endl; */
    /* for (int i = K-1; i >= 0; --i) cout << table[bity[i]]; */
    /* cout << endl; */

    /* Do sum */
    int lbit = zero;

    for (int i = 0; i < K; ++i) {
        bitans[i] = add_xor({lbit,bitx[i],bity[i]});
        u1 = add_and({bitx[i],bity[i]});
        u2 = add_and({bitx[i],lbit});
        u3 = add_and({bity[i],lbit});
        lbit = add_or({u1,u2,u3});
        if ((k&(1<<i))==0) {
            bitans[i] = add_not(bitans[i]);
        }
    }

    add_and(bitans);

    return;
}

#ifdef ONPC
void
generate()
{
    int h = 3;
    int w = 3;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            table.pb(0);
        }
    }
    table[0] = 1;
    table[2] = 1;

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cout << table[i*w+j];
        }
        cout << endl;
    }

    return;
}

void
solve()
{
    generate();
    construct_network(3,3,2);
    cout << table[sz(table)-1] << endl;
    cout << cnt1 << ' ' << cnt2 << endl;
}

int32_t
main()
{
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

컴파일 시 표준 에러 (stderr) 메시지

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:114:18: warning: unused variable 'u4' [-Wunused-variable]
  114 |     int u1,u2,u3,u4;
      |                  ^~

• 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