Submission #1067044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067044		jerzyk	Vision Program (IOI19_vision)	C++17	100 / 100	9 ms	1948 KiB

vision

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
int pos;
int tab[N];
vector<int> c0;

void C0(int n, int m)
{
    vector<int> xd;
    for(int i = 0; i < n * m; ++i) xd.pb(i);
    add_xor(xd);
    c0.pb(n * m);
}

vector<int> S(vector<int> a, vector<int> b)
{
    vector<int> ans;
    ++pos; ans.pb(pos);
    add_xor({a[0], b[0]});
    ++pos;
    add_and({a[0], b[0]});
    for(int i = 1; i < (int)a.size(); ++i)
    {
        int xd = pos;
        ++pos; ans.pb(pos);
        add_xor({xd, a[i], b[i]});
        ++pos; add_and({xd, a[i]});
        ++pos; add_and({xd, b[i]});
        ++pos; add_and({a[i], b[i]});

        ++pos; add_or({pos - 1, pos - 2, pos - 3});
    }
    ans.pb(pos);
    return ans;
}

vector<int> Fix(vector<int> a, int k)
{
    vector<int> ans;
    for(int i = 0; i < (int)a.size(); ++i)
    {
        ++pos; ans.pb(pos);
        if((1<<i)&k)
            add_or({a[i], c0[0]});
        else
            add_not(a[i]);
    }
    return ans;
}

vector<int> Query(int a, int b)
{
    vector<int> ans, x, y;
    if(a == b)
        {ans.pb(a); return ans;}
    x = Query(a, (a + b) / 2);
    y = Query((a + b) / 2 + 1, b);
    return S(x, y);
}

void construct_network(int n, int m, int K)
{
    int p2 = 1, w2 = 0;
    vector<int> s1, s2, sum;
    pos = n * m;
    while(p2 < n || p2 <= m){p2 *= 2; ++w2;}
    C0(n, m);

    int beg = pos + 1;
    for(int i = 1; i <= n; ++i)
    {
        ++pos;
        vector<int> cur;
        for(int j = m * (i - 1); j < m * i; ++j)
            cur.pb(j);
        if(i > 1)
            cur.pb(pos - 1);
        add_xor(cur);
    }
    for(int i = n + 1; i <= p2; ++i)
    {++pos; add_or(c0);}
    //cerr << beg << " " << pos << "\n";
    s1 = Query(beg, pos);

    beg = pos + 1;
    for(int j = 1; j <= m; ++j)
    {
        ++pos;
        vector<int> cur;
        for(int i = j - 1; i < m * n; i += m)
            cur.pb(i);
        if(j > 1)
            cur.pb(pos - 1);
        add_xor(cur);
    }
    for(int j = m + 1; j <= p2; ++j)
        {++pos; add_or(c0);}

    s2 = Query(beg, pos);
    sum = S(s1, s2);

    vector<int> final = Fix(sum, K);
    add_and(final);
}

• 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