oj.uz

Submission #978296

# Submission time Handle Problem Language Result Execution time Memory
978296 2024-05-09T05:51:24 Z sleepntsheep Broken Device (JOI17_broken_device) C
100 / 100
 217 ms 3580 KB 
#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]);
}


#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 2780 KB Output is correct - L* = 40
2 Correct 217 ms 2600 KB Output is correct - L* = 40
3 Correct 201 ms 2604 KB Output is correct - L* = 40
4 Correct 204 ms 3580 KB Output is correct - L* = 40
5 Correct 202 ms 2696 KB Output is correct - L* = 40
6 Correct 195 ms 2696 KB Output is correct - L* = 40
7 Correct 201 ms 2944 KB Output is correct - L* = 40
8 Correct 196 ms 2680 KB Output is correct - L* = 40
9 Correct 203 ms 3240 KB Output is correct - L* = 40
10 Correct 197 ms 2684 KB Output is correct - L* = 40
11 Correct 197 ms 2680 KB Output is correct - L* = 40
12 Correct 203 ms 2652 KB Output is correct - L* = 40
13 Correct 200 ms 2752 KB Output is correct - L* = 40
14 Correct 196 ms 2720 KB Output is correct - L* = 40
15 Correct 201 ms 2852 KB Output is correct - L* = 40
16 Correct 199 ms 2532 KB Output is correct - L* = 40
17 Correct 204 ms 2672 KB Output is correct - L* = 40
18 Correct 200 ms 2952 KB Output is correct - L* = 40
19 Correct 197 ms 2516 KB Output is correct - L* = 40
20 Correct 199 ms 2560 KB Output is correct - L* = 40
21 Correct 199 ms 2688 KB Output is correct - L* = 40
22 Correct 204 ms 2684 KB Output is correct - L* = 40
23 Correct 197 ms 2776 KB Output is correct - L* = 40
24 Correct 202 ms 2536 KB Output is correct - L* = 40
25 Correct 196 ms 2680 KB Output is correct - L* = 40
26 Correct 207 ms 2592 KB Output is correct - L* = 40
27 Correct 198 ms 2560 KB Output is correct - L* = 40
28 Correct 199 ms 2676 KB Output is correct - L* = 40
29 Correct 203 ms 3212 KB Output is correct - L* = 40
30 Correct 197 ms 2680 KB Output is correct - L* = 40
31 Correct 199 ms 2624 KB Output is correct - L* = 40
32 Correct 196 ms 2684 KB Output is correct - L* = 40
33 Correct 198 ms 2688 KB Output is correct - L* = 40
34 Correct 201 ms 3084 KB Output is correct - L* = 40
35 Correct 201 ms 2628 KB Output is correct - L* = 40
36 Correct 199 ms 2652 KB Output is correct - L* = 40
37 Correct 207 ms 2692 KB Output is correct - L* = 40
38 Correct 197 ms 2512 KB Output is correct - L* = 40
39 Correct 203 ms 2852 KB Output is correct - L* = 40
40 Correct 202 ms 2724 KB Output is correct - L* = 40