Submission #1155505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155505		jerzyk	Broken Device (JOI17_broken_device)	C++20	100 / 100	20 ms	1532 KiB

Anna

#include "Annalib.h"
#include <bits/stdc++.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 = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 200;
const int K = 60;
bool czy[N];
vector<int> cod[8];
int ans[N];

void DoC()
{
    cod[7] = {1, 1};
    cod[3] = {0, 1};
    cod[5] = {1, 0};
    cod[6] = {1};
    
    cod[1] = {1};
    cod[2] = {0, 0};
    cod[4] = {0};
}

void Anna(int _N, long long _X, int _K, int P[])
{
    DoC();
    int n = _N, k = _K; ll x = _X;
    for(int i = 1; i <= n; ++i)
    {
        ans[i] = 0;
        czy[i] = 0;
    }
    for(int i = 0; i < k; ++i)
        czy[P[i] + 1] = 1;
    vector<int> t;
    int il1 = 0;
    for(int i = 0; i < K; ++i)
    {
        int a = (bool)((1LL<<(ll)i) & x);
        il1 += a;
        t.pb(a);
    }
    t.pb(0);
    int j = 0;
    for(int i = 1; i + 2 <= n && j < K; i += 3)
    {
        int il = (int)czy[i] + (int)czy[i + 1] + (int)czy[i + 2];
        if(il > 1) continue;
        int akt = 0;
        for(int l = 0; l < 3; ++l)
            akt += (int)(czy[i + l] ^ 1) * (1<<l);
        int cur = 0;
        for(int l = 0; l < 8; ++l)
        {
            if((l & akt) != l) continue;
            bool czy = 1;
            for(int k = 0; k < (int)cod[l].size(); ++k)
                if(cod[l][k] != t[j + k]) czy = 0;
            if(czy == 1 && (int)cod[l].size() > (int)cod[cur].size())
                cur = l;

        }
        for(int l = 0; l < 3; ++l)
            ans[i + l] = (bool)((1<<l) & cur);
        j += (int)cod[cur].size();
    }
    /*for(int i = 1; i <= n; i += 3)
    {
        cout << ans[i] << ans[i + 1] << ans[i + 2];
        cout << " ";
    }
    cout << "\n";*/
    for(int i = 0; i < n; ++i)
        Set(i, ans[i + 1]);
}

Bruno

#include "Brunolib.h"
#include <bits/stdc++.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 = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1000'007;
const int K = 60;
vector<int> co[10];

void Do()
{
    co[7] = {1, 1};
    co[3] = {0, 1};
    co[5] = {1, 0};
    co[6] = {1};
    
    co[1] = {1};
    co[2] = {0, 0};
    co[4] = {0};
}

long long Bruno( int _N, int A[])
{
    Do();
    int n = _N; ll ans = 0LL;
    vector<int> cur;
    for(int i = 0; i + 2 < n && (int)cur.size() < K; i += 3)
    {
        int a = 0;
        for(int j = 0; j < 3; ++j)
            a += A[i + j] * (1<<j);
        for(int j = 0; j < (int)co[a].size(); ++j)
            cur.pb(co[a][j]);
    }
    /*cerr << "B: \n";
    for(int i = 0; i < (int)cur.size(); ++i)
        cerr << cur[i] << " ";
    cerr << "\n";*/
    for(int i = 0; i < min(K, (int)cur.size()); ++i)
    {
        ans += (1LL<<(ll)i) * (ll)cur[i];
    }
    //cerr << ans << "\n";
    return ans;
}

• Subtask 1: 100 / 100