oj.uz

Submission #549509

# Submission time Handle Problem Language Result Execution time Memory
549509 2022-04-16T01:42:14 Z LucaDantas Broken Device (JOI17_broken_device) C++17
100 / 100
 68 ms 2720 KB 
#include "Annalib.h"
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 150;

mt19937_64 rng_64(1012);

long long rnd() { return rng_64() & ((1ll<<60)-1); } // construo um numero aleatorio de 60 bits

bool foi = 0;
long long v[maxn];

void build() {
	foi = 1;
	for(int i = 0; i < maxn; i++)
		v[i] = rnd();
}

vector<pair<long long, bitset<maxn>>> basis;

bitset<maxn> ids;

void insert(long long x, int ID) {
	ids.reset();
	if(ID != -1) ids.set(ID);

	for(auto [y, usados] : basis) {
		if((x^y) < x) {
			x ^= y;
			ids ^= usados;
		}
	}

	if(x) basis.push_back({x, ids});
}

void Anna(int N, long long X, int K, int P[]) {
	if(!foi) build();
	
	basis.clear();
	for(int i = 0, ptr = 0; i < maxn; i++) {
		if(ptr < K && P[ptr] == i) { ++ptr; continue; }
		insert(v[i], i);
	}

	insert(X, -1);
	for(int i = 0; i < N; i++)
		Set(i, ids.test(i));
}

#include "Brunolib.h"
#include <cstdio>
#include <random>

namespace sla {

constexpr int maxn = 150;

std::mt19937_64 rng_64(1012);

long long rnd() { return rng_64() & ((1ll<<60)-1); } // construo um numero aleatorio de 60 bits

bool foi = 0;
long long v[maxn];

void build() {
	foi = 1;
	for(int i = 0; i < maxn; i++)
		v[i] = rnd();
}
}

long long Bruno(int N, int A[]) {
	if(!sla::foi) sla::build();
	
	long long ans = 0;
	for(int i = 0; i < N; i++)
		if(A[i]) ans ^= sla::v[i];
	return ans;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 2488 KB Output is correct - L* = 40
2 Correct 61 ms 2560 KB Output is correct - L* = 40
3 Correct 63 ms 2552 KB Output is correct - L* = 40
4 Correct 63 ms 2496 KB Output is correct - L* = 40
5 Correct 63 ms 2460 KB Output is correct - L* = 40
6 Correct 60 ms 2608 KB Output is correct - L* = 40
7 Correct 62 ms 2424 KB Output is correct - L* = 40
8 Correct 61 ms 2560 KB Output is correct - L* = 40
9 Correct 61 ms 2600 KB Output is correct - L* = 40
10 Correct 62 ms 2568 KB Output is correct - L* = 40
11 Correct 60 ms 2428 KB Output is correct - L* = 40
12 Correct 60 ms 2416 KB Output is correct - L* = 40
13 Correct 68 ms 2480 KB Output is correct - L* = 40
14 Correct 67 ms 2704 KB Output is correct - L* = 40
15 Correct 64 ms 2692 KB Output is correct - L* = 40
16 Correct 64 ms 2720 KB Output is correct - L* = 40
17 Correct 61 ms 2636 KB Output is correct - L* = 40
18 Correct 62 ms 2472 KB Output is correct - L* = 40
19 Correct 61 ms 2424 KB Output is correct - L* = 40
20 Correct 65 ms 2544 KB Output is correct - L* = 40
21 Correct 60 ms 2468 KB Output is correct - L* = 40
22 Correct 62 ms 2468 KB Output is correct - L* = 40
23 Correct 61 ms 2516 KB Output is correct - L* = 40
24 Correct 63 ms 2480 KB Output is correct - L* = 40
25 Correct 61 ms 2536 KB Output is correct - L* = 40
26 Correct 62 ms 2472 KB Output is correct - L* = 40
27 Correct 61 ms 2404 KB Output is correct - L* = 40
28 Correct 64 ms 2424 KB Output is correct - L* = 40
29 Correct 66 ms 2596 KB Output is correct - L* = 40
30 Correct 64 ms 2644 KB Output is correct - L* = 40
31 Correct 60 ms 2404 KB Output is correct - L* = 40
32 Correct 61 ms 2520 KB Output is correct - L* = 40
33 Correct 62 ms 2416 KB Output is correct - L* = 40
34 Correct 63 ms 2532 KB Output is correct - L* = 40
35 Correct 62 ms 2468 KB Output is correct - L* = 40
36 Correct 60 ms 2616 KB Output is correct - L* = 40
37 Correct 60 ms 2528 KB Output is correct - L* = 40
38 Correct 63 ms 2524 KB Output is correct - L* = 40
39 Correct 61 ms 2516 KB Output is correct - L* = 40
40 Correct 61 ms 2464 KB Output is correct - L* = 40