제출 #213465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
213465		tri	Broken Device (JOI17_broken_device)	C++14	0 / 100	2099 ms	4856 KiB

Anna

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second


int N;

const int MAXN = 155;
const int MAXV = 1 << 20;

int data[MAXN];

mt19937 re(1377);
uniform_int_distribution<int> uniform_dist(0, MAXV);

int group[MAXN];
vi mem[3];

int broken[MAXN];

int pos[MAXV];

int output[MAXN];

void init() {
    for (int i = 0; i < N; i++) {
        data[i] = uniform_dist(re);
    }

    fill(group, group + N / 3, 0);
    fill(group + N / 3, group + 2 * N / 3, 1);
    fill(group + 2 * N / 3, group + N, 2);

    shuffle(group, group + N, re);

    for (int i = 0; i < 3; i++) {
        mem[i].clear();
    }

    for (int i = 0; i < N; i++) {
        if (!broken[i]) {
            mem[group[i]].pb(i);
        }
    }
}

// assert 20 bit frag
void calc(int group, int frag) {
    memset(pos, 0, sizeof(pos));

    vi &cMem = mem[group];
    assert(cMem.size() >= 20);

    if (cMem.size() >= 40) {
        cMem.erase(cMem.end() - (cMem.size() - 40), cMem.end());
    }

    int hSize = cMem.size() / 2;

//    cout << hSize << endl;

    for (int bSet = 0; bSet < (1 << hSize); bSet++) {
        int partial = 0;
        for (int j = 0; j < hSize; j++) {
            if (bSet & (1 << j)) {
                partial ^= data[cMem[j]];
            }
        }
        pos[partial] = bSet;
    }

    int rem = cMem.size() - hSize;

    for (int bSet = 0; bSet < (1 << rem); bSet++) {
        int partial = 0;
        for (int j = 0; j < rem; j++) {
            if (bSet & (1 << j)) {
                partial ^= data[cMem[hSize + j]];
            }
        }

        int desire = frag ^partial;
        if (pos[desire]) {
            int fSet = pos[desire];

            for (int j = 0; j < hSize; j++) {
                if (fSet & (1 << j)) {
                    output[cMem[j]] = 1;
                }
            }

            for (int j = 0; j < rem; j++) {
                if (bSet & (1 << j)) {
                    output[cMem[hSize + j]] = 1;
                }
            }

            return;
        }
    }

    assert(false);
}


void Anna(int iN, ll X, int K, int P[]) {
    N = iN;
    assert(N == 150);

    fill(broken, broken + N, 0);
    for (int i = 0; i < K; i++) {
        broken[P[i]] = true;
    }

//    cout << "read" << endl;

    init();

//    cout << "init" << endl;

    memset(output, 0, sizeof(output));

    for (int g = 0; g < 3; g++) {
        int frag = X & ((1 << 20) - 1);
        calc(g, frag);

        X >>= 20;
    }

    for (int i = 0; i < N; i++) {
        Set(i, output[i]);
    }

//    cout << "done" << endl;
//    ps(mem[0]);
}

Bruno

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = true;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;


namespace rdup {

    int N;

    const int MAXN = 155;
    const int MAXV = 1 << 20;

    int data[MAXN];

    mt19937 re(1377);
    uniform_int_distribution<int> uniform_dist(0, MAXV);

    int group[MAXN];
    vi mem[3];

    int broken[MAXN];

    void init() {
        for (int i = 0; i < N; i++) {
            data[i] = uniform_dist(re);
        }

        fill(group, group + N / 3, 0);
        fill(group + N / 3, group + 2 * N / 3, 1);
        fill(group + 2 * N / 3, group + N, 2);

        shuffle(group, group + N, re);

        for (int i = 0; i < 3; i++) {
            mem[i].clear();
        }

        for (int i = 0; i < N; i++) {
            if (!broken[i]) {
                mem[group[i]].pb(i);
            }
        }
    }
}

ll Bruno(int iN, int A[]) {
    rdup::N = iN;
    assert(rdup::N == 150);

    fill(rdup::broken, rdup::broken + rdup::N, 0);

    rdup::init();

//    ps(rdup::mem[0]);

    ll ans = 0;
    for (int group = 2; group >= 0; group--) {
        ans <<= 20;
        ll frag = 0;
        for (int i : rdup::mem[group]) {
            if (A[i]) {
                frag ^= rdup::data[i];
            }
        }
        ans |= frag;
    }
//    cout << ans << endl;
    return ans;
}

• Subtask 1: 0 / 100