Submission #978296

#	Time	Username	Problem	Language	Result	Execution time	Memory
978296		sleepntsheep	Broken Device (JOI17_broken_device)	C11	100 / 100	217 ms	3580 KiB

Anna

#include "Annalib.h"
#include<assert.h>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef long long i64;
static i64 vecspace[150];
static void init() {
    srand(86868686u);
    for(int i=0;i<150;++i)
    {
        vecspace[i] = rand();
        vecspace[i] = vecspace[i] * rand() % (1llu << 60);
        vecspace[i] = vecspace[i] * rand() % (1llu << 60);
    }
}

i64 basis[64];
char basis_toggle[64][110];
int map[150], rvmap[110];

void basis_add(i64 x,int id)
{
    char toggle[110]={0};
    toggle[id] = 1;

    for(i64 j=60;j>=0;--j)
    {
        if(0==((x>>j)&1))
            continue;
        if (basis[j])
        {
            for (int k=0;k<110;++k)
                toggle[k] ^= basis_toggle[j][k];
            x ^= basis[j];
        }
        else
        {
            basis[j] = x;
            memcpy(basis_toggle[j], toggle, sizeof toggle);
            return;
        }
    }
}

void Anna( int N, long long X, int K, int P[] ){
    init();
    init();

    int skillissue[150]={0};
    for(int i=0;i<K;++i)skillissue[P[i]]=1;

    for(int c1=0,i=0;i<150&&c1<110;++i)
        if(skillissue[i]==0)rvmap[map[i]=c1]=i,++c1;

    memset(basis,0,sizeof basis);
    memset(basis_toggle,0,sizeof basis_toggle);

    for(int i=0;i<150;++i)
        if(!skillissue[i] && map[i]<110)
            basis_add(vecspace[i], map[i]);

    int encode[150]={0};
    for(i64 j=60;j>=0;--j)
    {
        if(0==((X>>j)&1))
            continue;
        X ^= basis[j];
        for(int k=0;k<110;++k)
            encode[rvmap[k]] ^= (int)basis_toggle[j][k];
    }

    for(int i=0;i<150;++i) Set(i,encode[i]);
}

Bruno

#include "Brunolib.h"
#include<stdio.h>
#include<stdlib.h>

typedef long long i64;
static i64 vecspace[150];
static void init() {
    srand(86868686u);
    for(int i=0;i<150;++i)
    {
        vecspace[i] = rand();
        vecspace[i] = vecspace[i] * rand() % (1llu << 60);
        vecspace[i] = vecspace[i] * rand() % (1llu << 60);
    }
}

long long Bruno( int N, int A[] ){
    init();
    long long X=0;
    for(int i=0;i<150;++i)if(A[i])
        X^=vecspace[i];
    return X;
}

• Subtask 1: 100 / 100