Submission #551454

#	Time	Username	Problem	Language	Result	Execution time	Memory
551454		BalintR	Broken Device 2 (JOI22_device2)	C++17	40 / 100	679 ms	26868 KiB

Anna

#include <bits/stdc++.h>
using namespace std;
#include "Anna.h"

namespace {
    typedef unsigned uint;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int, int> pii;
    typedef pair<ll, ll> pll;
    typedef vector<int> vi;
    typedef vector<pii> vpii;
    typedef complex<double> cmplx;
    template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) (v).begin(), (v).end()
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound((v).begin(), (v).end(), x) - (v).begin())
#define ubv(v, x) (upper_bound((v).begin(), (v).end(), x) - (v).begin())
    template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
    const int INF = 0x3f3f3f3f;
    const ll LLINF = 0x3f3f3f3f3f3f3f3f;
    const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << arr[_i]; cerr << endl;}

    const int MX = 3.9e6;
    const int MN = 2000;
}

int Declare(){
    return MN;
}

pair<vi, vi> Anna(ll input){
    ll in1 = input & 511;
    ll in2 = (input >> 9) & 511;
    ll in3 = input >> 18;
    /*dbg(in1);
    dbg(in2);
    dbg(in3);*/

    vi s1, s2;
    FR(i, 9) FR(j, 1<<i) s1.pb((in1 >> i) & 1);
    FR(i, 9) FR(j, 1<<i) s2.pb((in2 >> i) & 1);
    reverse(ALL(s2));

    ll x = in3;
    int len = 0, pop = -1;
    while(len < MN){
        int dif = len*2;
        if(x < dif){
            pop = x;
            break;
        }
        x -= dif;
        len++;
    }

    //dbg(len);

    vi v1(len), v2(len);
    FR(i, len) if(pop) v1[i] = 1, pop--;
    FR(i, len) if(pop) v2[i] = 1, pop--;

    vi res1 = vi(s1);
    for(int a : v1) res1.pb(a);
    for(int a : s2) res1.pb(a);
    vi res2 = vi(s1);
    for(int a : v2) res2.pb(a);
    for(int a : s2) res2.pb(a);
    //dbg(SZ(res1));
    //dbg(SZ(res2));
    return {res1, res2};
}

Bruno

#include <bits/stdc++.h>
using namespace std;
#include "Bruno.h"

namespace {
    typedef unsigned uint;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int, int> pii;
    typedef pair<ll, ll> pll;
    typedef vector<int> vi;
    typedef vector<pii> vpii;
    typedef complex<double> cmplx;
    template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) (v).begin(), (v).end()
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound((v).begin(), (v).end(), x) - (v).begin())
#define ubv(v, x) (upper_bound((v).begin(), (v).end(), x) - (v).begin())
    template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
    const int INF = 0x3f3f3f3f;
    const ll LLINF = 0x3f3f3f3f3f3f3f3f;
    const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << arr[_i]; cerr << endl;}

    const int MX = 3.9e6;
    const int MN = 2000;
}


ll Bruno(vi u){
    int n = SZ(u);
    int pop = 0;

    ll v1 = 0;
    vi inds[2];
    int offs[2] = {0, 0};
    FR(i, n) inds[u[i]].pb(i);
    inds[0].pb(INF); inds[1].pb(INF);

    FR(i, 9){
        int val = inds[1][offs[1]] < inds[0][offs[0]];
        v1 |= val << i;
        pop -= val * (2 << i);
        offs[val] += 2 << i;
    }
    reverse(ALL(u));

    ll v2 = 0;
    inds[0].clear(), inds[1].clear();
    offs[0] = offs[1] = 0;
    FR(i, n) inds[u[i]].pb(i);
    inds[0].pb(INF); inds[1].pb(INF);

    FR(i, 9){
        int val = inds[1][offs[1]] < inds[0][offs[0]];
        v2 |= val << i;
        pop -= val * (2 << i);
        offs[val] += 2 << i;
    }
    reverse(ALL(u));

    ll v3 = 0;
    int fullLen = SZ(u) - 511*4;
    int len = 0;
    while(len < fullLen/2){
        int dif = len*2;
        v3 += dif;
        len++;
    }

    for(int a : u) pop += a;
    assert(pop >= 0);
    v3 += pop;

    /*dbg(v1);
    dbg(v2);
    dbg(v3);*/
    return (v3 << 18) | (v2 << 9) | v1;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 3 / 3
• Subtask 4: 12 / 12
• Subtask 5: 15 / 15
• Subtask 6: 0 / 60