oj.uz

Submission #978298

# Submission time Handle Problem Language Result Execution time Memory
978298 2024-05-09T05:53:19 Z sleepntsheep Broken Device (JOI17_broken_device) C
100 / 100
 202 ms 3196 KB 
#include "Annalib.h"
#include<string.h>
#include<stdlib.h>

static long long vecspace[150];
static void init() {
    /* https://www.iq.com/album/86%EF%BC%8Deighty-six%EF%BC%8D-2021-2aef2fzzzvp?lang=en_us */
    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 basis[64];
char basis_toggle[64][110];
int map[150], rvmap[110];

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

    for(long long 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();

    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(long long 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<stdlib.h>

static long long vecspace[150];
static void init() {
    /* https://www.iq.com/album/86%EF%BC%8Deighty-six%EF%BC%8D-2021-2aef2fzzzvp?lang=en_us */
    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 190 ms 2316 KB Output is correct - L* = 40
2 Correct 194 ms 2812 KB Output is correct - L* = 40
3 Correct 194 ms 2292 KB Output is correct - L* = 40
4 Correct 194 ms 2388 KB Output is correct - L* = 40
5 Correct 197 ms 2628 KB Output is correct - L* = 40
6 Correct 191 ms 2324 KB Output is correct - L* = 40
7 Correct 192 ms 2312 KB Output is correct - L* = 40
8 Correct 197 ms 3196 KB Output is correct - L* = 40
9 Correct 195 ms 2284 KB Output is correct - L* = 40
10 Correct 199 ms 2492 KB Output is correct - L* = 40
11 Correct 196 ms 2320 KB Output is correct - L* = 40
12 Correct 191 ms 2292 KB Output is correct - L* = 40
13 Correct 192 ms 2616 KB Output is correct - L* = 40
14 Correct 191 ms 2364 KB Output is correct - L* = 40
15 Correct 194 ms 2432 KB Output is correct - L* = 40
16 Correct 194 ms 2400 KB Output is correct - L* = 40
17 Correct 193 ms 2316 KB Output is correct - L* = 40
18 Correct 192 ms 2300 KB Output is correct - L* = 40
19 Correct 196 ms 2844 KB Output is correct - L* = 40
20 Correct 193 ms 2468 KB Output is correct - L* = 40
21 Correct 193 ms 2300 KB Output is correct - L* = 40
22 Correct 200 ms 2776 KB Output is correct - L* = 40
23 Correct 191 ms 2400 KB Output is correct - L* = 40
24 Correct 191 ms 2428 KB Output is correct - L* = 40
25 Correct 190 ms 2344 KB Output is correct - L* = 40
26 Correct 190 ms 2468 KB Output is correct - L* = 40
27 Correct 202 ms 2428 KB Output is correct - L* = 40
28 Correct 193 ms 2428 KB Output is correct - L* = 40
29 Correct 194 ms 2460 KB Output is correct - L* = 40
30 Correct 195 ms 2688 KB Output is correct - L* = 40
31 Correct 195 ms 2384 KB Output is correct - L* = 40
32 Correct 191 ms 2504 KB Output is correct - L* = 40
33 Correct 196 ms 2688 KB Output is correct - L* = 40
34 Correct 193 ms 2348 KB Output is correct - L* = 40
35 Correct 194 ms 2428 KB Output is correct - L* = 40
36 Correct 191 ms 2300 KB Output is correct - L* = 40
37 Correct 190 ms 2284 KB Output is correct - L* = 40
38 Correct 192 ms 2464 KB Output is correct - L* = 40
39 Correct 192 ms 2396 KB Output is correct - L* = 40
40 Correct 191 ms 2448 KB Output is correct - L* = 40