제출 #1363832

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1363832		xorshift	마술쇼 (APIO24_show)	C++20	100 / 100	84 ms	924 KiB

Alice

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

using ll = long long;
using vint = vector<int>;
using vll = vector<ll>;
using pint = pair<int, int>;
using vpint = vector<pint>;

#define fi first
#define se second 
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a)-1; i >= (b); i--)

const int BITS = 60000;
const int VBITS = 60;
const int n = 5000;

const int seed = 18342;
mt19937_64 rng(seed);

vpint Alice(){
    ll x = setN(n);

    bitset<BITS> br, bv(x);
    rep(i, BITS/VBITS) {
        br |= bv << i*VBITS;
    }
    bitset<BITS> b;
    vint to(BITS); iota(all(to), 0);
    rng.seed(seed);
    shuffle(all(to), rng);
    rep(i, BITS) b[to[i]] = br[i];

    vint p(n, -1);
    int b_count = 0;
    rrep(i, n) {
        if (i == 0) continue;
        int b_size = __lg(i);
        int j = ((b >> b_count) << (BITS-b_size) >> (BITS-b_size)).to_ulong();
        p[i] = j;
        b_count += b_size;
    }
    vpint res;
    rep(i, n) if (p[i] != -1) {
        vint map(i); iota(all(map), 1);
        rng.seed(seed+i);
        shuffle(all(map), rng);
        res.push_back({map[p[i]], i+1});
    }
    return res;
}

Bob

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

using ll = long long;
using vint = vector<int>;
using vll = vector<ll>;
using pint = pair<int, int>;
using vpint = vector<pint>;

#define fi first
#define se second 
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a)-1; i >= (b); i--)

const int BITS = 60000;
const int VBITS = 60;
const int n = 5000;

const int seed = 18342;
mt19937_64 rng(seed);

ll Bob(vpint V){
    vint p(n, -1);
    sort(all(V), [](pint& a, pint& b) { return a.se < b.se; });
    for (auto& [mj, i1]: V) {
        int i = i1-1;
        vint map = vint(i); iota(all(map), 1);
        rng.seed(seed+i);
        shuffle(all(map), rng);
        vint remap(i+1); rep(x, i) remap[map[x]] = x;
        int j = remap[mj];
        p[i] = j;
    }
	bitset<BITS> br, b_recr;
    int b_count = 0;
    rrep(i, n) {
        if (i == 0) continue;
        int b_size = __lg(i);
        int j = p[i];
        if (j != -1) {
            bitset<BITS> bv(j);
            br |= bv << b_count;
            bitset<BITS> rv((1 << b_size)-1);
            b_recr |= rv << b_count;
        }
        b_count += b_size;
    }
    bitset<BITS> b, b_rec;
    vint to(BITS); iota(all(to), 0);
    rng.seed(seed);
    shuffle(all(to), rng);
    rep(i, BITS) b[i] = br[to[i]], b_rec[i] = b_recr[to[i]];

    bitset<VBITS> xb, xb_rec;
    rep(i, BITS/VBITS) {
        rep(j, VBITS) {
            int pos = i*VBITS+j;
            if (b_rec[pos]) xb_rec[j] = b_rec[pos];
            if (b_rec[pos]) xb[j] = b[pos];
        }
    }
    if (xb_rec.count() != VBITS) while (true) {}
    else {
        ll x = xb.to_ullong();
        return x;
    }
}

• 서브태스크 1: 5 / 5
• 서브태스크 2: 30 / 30
• 서브태스크 3: 65 / 65