제출 #1127632

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127632		rl_	Broken Device (JOI17_broken_device)	C++20	0 / 100	2094 ms	600 KiB

Anna

#include "Annalib.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef array<ll, 2> pii;
typedef array<ll, 3> tii;
typedef vector<pii> vpii;
typedef double lf;
#define V vector
#define PQ priority_queue
#define forf(i, s, e) for(ll i=s; i<e; i++)
#define forb(i, s, e) for(ll i=s-1; i>=e; i--)
#define pb push_back
#define sortv(v) sort(v.begin(), v.end())
#define sortc(v, cmp) sort(v.begin(), v.end(), cmp)
#define all(v) v.begin(), v.end()
const ll mod=1e9+7, MOD=998244353;
const ll dir4[4][2]={{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
const ll dir8[8][2]={{0, 1}, {1, 0}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
const ll inf=2147483647, linf=9223372036854775807;
const double pi=acos(-1), E=2.718281828459;
ll gcd(ll a, ll b){return b?gcd(b, a%b):a;}


ll M=32000;
vvi T={{8, 9, 10, 11, 29, 30, 42, 47, 61, 68, 71, 78, 79, 80, 83, 89, 94, 104, 107, 111, 114, 115, 116, 117, 121, 122, 123, 124, 126, 127, 132, 134, 138, 140, 143, 145, 146, 148},
{2, 4, 14, 17, 23, 25, 27, 33, 34, 36, 37, 40, 43, 46, 51, 52, 58, 62, 64, 66, 69, 70, 72, 74, 76, 82, 85, 87, 88, 95, 97, 98, 100, 105, 106, 110, 113, 149},
{5, 12, 13, 18, 19, 21, 26, 28, 31, 32, 35, 41, 49, 50, 54, 55, 56, 63, 67, 73, 75, 84, 90, 93, 96, 103, 109, 119, 120, 128, 130, 131, 133, 135, 136, 137, 142},
{0, 1, 3, 6, 7, 15, 16, 20, 22, 24, 38, 39, 44, 45, 48, 53, 57, 59, 60, 65, 77, 81, 86, 91, 92, 99, 101, 102, 108, 112, 118, 125, 129, 139, 141, 144, 147}};
V<bool> PC(150);
vi rnd={24925, 763, 31335, 21632, 17798, 8755, 13273, 8977, 22368, 10561, 18719, 17203, 14687, 5461, 17138, 16073, 8618, 2184, 11611, 23246, 17953, 4812, 976, 25322, 18847, 31267, 10399, 21315, 3708, 21263, 27536, 21654, 4695, 74, 25541, 16006, 14098, 22709, 8422, 5172, 7453, 18070, 30587, 12047, 29432, 19199, 27801, 3054, 24051, 25226, 1217, 28252, 24633, 24651, 31237, 20018, 24588, 26631, 7532, 17260, 13394, 22690, 26520, 25653, 23121, 15063, 31910, 18756, 14519, 2092, 10070, 11371, 5085, 24100, 3948, 21869, 5964, 29110, 12118, 18705, 6273, 22270, 19726, 28276, 30445, 28979, 31298, 7843, 15680, 7897, 24499, 21097, 26599, 30263, 22491, 25190, 29907, 9740, 7378, 3425, 8317, 20094, 3442, 14560, 29735, 26195, 19898, 8181, 2404, 99, 18032, 25690, 9946, 1357, 18442, 13760, 6727, 13674, 21711, 869, 29634, 1791, 22074, 27621, 1604, 13495, 16799, 24402, 20838, 4176, 28688, 10118, 14444, 28052, 11650, 19128, 10883, 14731, 17196, 31822, 8263, 4591, 304, 4082, 4744, 28896, 2941, 8936, 20046, 16601};

void _DP(ll ind, ll mp){
    ll ts=T[ind].size();
    V<V<bool>> DP(ts);
    forf(i, 0, ts) DP[i].resize(M);

    DP[0][0]=1; DP[0][rnd[T[ind][0]]]=!PC[T[ind][0]];
    ll _cnt=!PC[T[ind][0]];
    forf(i, 1, ts){
        forf(j, 0, M) DP[i][j]=DP[i-1][j]||(PC[T[ind][i]]==0 && DP[i-1][(j-rnd[T[ind][i]]+M)%M]);
        ll cnt=0; forf(j, 0, M) cnt+=DP[i][j];
    }
    ll N=mp;
    forb(i, ts, 1){
        if(DP[i-1][N] || PC[T[ind][i]]==1) Set(T[ind][i], 0);
        else Set(T[ind][i], 1), N=(N-rnd[T[ind][i]]+M)%M;
    }
    if(N==0) Set(T[ind][0], 0);
    else Set(T[ind][0], 1), N=(N-rnd[T[ind][0]]+M)%M;
    return;
}

void Anna(int N, ll X, int K, int P[]){
    forf(i, 0, 150) PC[i]=0;
    forf(i, 0, K) PC[P[i]]=1;
    ll r=0; forf(i, 0, 150) r+=PC[i];
    forf(i, 0, 4) _DP(i, X%M), X/=M;
}

Bruno

#include "Brunolib.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef array<ll, 2> pii;
typedef array<ll, 3> tii;
typedef vector<pii> vpii;
typedef double lf;
#define V vector
#define PQ priority_queue
#define forf(i, s, e) for(ll i=s; i<e; i++)
#define forb(i, s, e) for(ll i=s-1; i>=e; i--)
#define pb push_back
#define sortv(v) sort(v.begin(), v.end())
#define sortc(v, cmp) sort(v.begin(), v.end(), cmp)
#define all(v) v.begin(), v.end()
const ll mod=1e9+7, MOD=998244353;
const ll dir4[4][2]={{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
const ll dir8[8][2]={{0, 1}, {1, 0}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
const ll inf=2147483647, linf=9223372036854775807;
const double pi=acos(-1), E=2.718281828459;
ll gcd(ll a, ll b){return b?gcd(b, a%b):a;}


ll M=32000;
vvi T={{8, 9, 10, 11, 29, 30, 42, 47, 61, 68, 71, 78, 79, 80, 83, 89, 94, 104, 107, 111, 114, 115, 116, 117, 121, 122, 123, 124, 126, 127, 132, 134, 138, 140, 143, 145, 146, 148},
{2, 4, 14, 17, 23, 25, 27, 33, 34, 36, 37, 40, 43, 46, 51, 52, 58, 62, 64, 66, 69, 70, 72, 74, 76, 82, 85, 87, 88, 95, 97, 98, 100, 105, 106, 110, 113, 149},
{5, 12, 13, 18, 19, 21, 26, 28, 31, 32, 35, 41, 49, 50, 54, 55, 56, 63, 67, 73, 75, 84, 90, 93, 96, 103, 109, 119, 120, 128, 130, 131, 133, 135, 136, 137, 142},
{0, 1, 3, 6, 7, 15, 16, 20, 22, 24, 38, 39, 44, 45, 48, 53, 57, 59, 60, 65, 77, 81, 86, 91, 92, 99, 101, 102, 108, 112, 118, 125, 129, 139, 141, 144, 147}};
V<bool> PC(150);
vi rnd={24925, 763, 31335, 21632, 17798, 8755, 13273, 8977, 22368, 10561, 18719, 17203, 14687, 5461, 17138, 16073, 8618, 2184, 11611, 23246, 17953, 4812, 976, 25322, 18847, 31267, 10399, 21315, 3708, 21263, 27536, 21654, 4695, 74, 25541, 16006, 14098, 22709, 8422, 5172, 7453, 18070, 30587, 12047, 29432, 19199, 27801, 3054, 24051, 25226, 1217, 28252, 24633, 24651, 31237, 20018, 24588, 26631, 7532, 17260, 13394, 22690, 26520, 25653, 23121, 15063, 31910, 18756, 14519, 2092, 10070, 11371, 5085, 24100, 3948, 21869, 5964, 29110, 12118, 18705, 6273, 22270, 19726, 28276, 30445, 28979, 31298, 7843, 15680, 7897, 24499, 21097, 26599, 30263, 22491, 25190, 29907, 9740, 7378, 3425, 8317, 20094, 3442, 14560, 29735, 26195, 19898, 8181, 2404, 99, 18032, 25690, 9946, 1357, 18442, 13760, 6727, 13674, 21711, 869, 29634, 1791, 22074, 27621, 1604, 13495, 16799, 24402, 20838, 4176, 28688, 10118, 14444, 28052, 11650, 19128, 10883, 14731, 17196, 31822, 8263, 4591, 304, 4082, 4744, 28896, 2941, 8936, 20046, 16601};


ll rdp(ll ind, int A[]){
    ll r=0;
    forf(i, 0, T[ind].size()) r+=A[T[ind][i]]*rnd[T[ind][i]];
    return r%M;
}

ll Bruno(int n, int A[]){
    ll ret=0;
    forb(i, 4, 0) ret=(ret*M+rdp(i, A));
    return ret;
}

• Subtask 1: 0 / 100