oj.uz

Submission #804626

# Submission time Handle Problem Language Result Execution time Memory
804626 2023-08-03T10:32:38 Z sentheta Broken Device (JOI17_broken_device) C++17
100 / 100
 81 ms 2856 KB 
#include "Annalib.h"
#ifdef VANWIJ
	#define DBG 1
#else
	#include"bits/stdc++.h"
	#define DBG 0
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second


#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)

#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}

static const int N = 150;

static bool usable[N];

static V<Int> a;
static void build(){
	if(!a.empty()) return;
	mt19937_64 rng(9876);
	a.resize(N);
	rep(i,0,N){
		a[i] = rng();
		if(a[i] < 0) a[i] = abs(a[i]);
	}
}

struct Base{
	Int x;
	bitset<N> comp;
};
bool operator<(const Base &p,const Base &q){
	return p.x < q.x;
}

void Anna(int _N,Int z,int k,int p[]){
	build();
	
	rep(i,0,N){
		usable[i] = 1;
	}
	rep(i,0,k){
		usable[p[i]] = 0;
	}
	
	
	// xor basis
	V<Base> basis;
	rep(i,0,N) if(usable[i]){
		Int x = a[i];
		bitset<N> c;
		c[i] = 1;
		
		for(auto&[y,comp] : basis){
			if(x&1LL<<msb(y)){
				x ^= y;
				c ^= comp;
			}
		}
		
		if(x!=0){
			basis.push_back({x,c});
			
			sort(all(basis));
			reverse(all(basis));
		}
	}
	
	
	bitset<N> ans;
	for(auto&[y,comp] : basis){
		if(z&1LL<<msb(y)){
			z ^= y;
			ans ^= comp;
		}
	}
	
	rep(i,0,N){
		Set(i, ans[i]);
	}
	
	
	// for(int i=0; i<N; i++) Set(i, 0);
}

#include "Brunolib.h"
#ifdef VANWIJ
	#define DBG 1
#else
	#include"bits/stdc++.h"
	#define DBG 0
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(9876);

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)

#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}

static const int N = 150;


static V<Int> a;
static void build(){
	if(!a.empty()) return;
	mt19937_64 rng(9876);
	a.resize(N);
	rep(i,0,N){
		a[i] = rng();
		if(a[i] < 0) a[i] = abs(a[i]);
	}
}


Int Bruno(int _N,int b[]){
	build();
	
	Int x = 0;
	rep(i,0,N) if(b[i]){
		x ^= a[i];
	}
	return x;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2416 KB Output is correct - L* = 40
2 Correct 76 ms 2520 KB Output is correct - L* = 40
3 Correct 73 ms 2512 KB Output is correct - L* = 40
4 Correct 76 ms 2476 KB Output is correct - L* = 40
5 Correct 72 ms 2492 KB Output is correct - L* = 40
6 Correct 72 ms 2468 KB Output is correct - L* = 40
7 Correct 80 ms 2460 KB Output is correct - L* = 40
8 Correct 73 ms 2432 KB Output is correct - L* = 40
9 Correct 72 ms 2444 KB Output is correct - L* = 40
10 Correct 78 ms 2400 KB Output is correct - L* = 40
11 Correct 74 ms 2460 KB Output is correct - L* = 40
12 Correct 72 ms 2648 KB Output is correct - L* = 40
13 Correct 71 ms 2388 KB Output is correct - L* = 40
14 Correct 79 ms 2400 KB Output is correct - L* = 40
15 Correct 78 ms 2572 KB Output is correct - L* = 40
16 Correct 76 ms 2444 KB Output is correct - L* = 40
17 Correct 71 ms 2500 KB Output is correct - L* = 40
18 Correct 71 ms 2464 KB Output is correct - L* = 40
19 Correct 73 ms 2528 KB Output is correct - L* = 40
20 Correct 81 ms 2580 KB Output is correct - L* = 40
21 Correct 74 ms 2508 KB Output is correct - L* = 40
22 Correct 71 ms 2548 KB Output is correct - L* = 40
23 Correct 72 ms 2416 KB Output is correct - L* = 40
24 Correct 71 ms 2520 KB Output is correct - L* = 40
25 Correct 77 ms 2532 KB Output is correct - L* = 40
26 Correct 73 ms 2548 KB Output is correct - L* = 40
27 Correct 71 ms 2528 KB Output is correct - L* = 40
28 Correct 76 ms 2480 KB Output is correct - L* = 40
29 Correct 73 ms 2552 KB Output is correct - L* = 40
30 Correct 72 ms 2524 KB Output is correct - L* = 40
31 Correct 78 ms 2520 KB Output is correct - L* = 40
32 Correct 72 ms 2532 KB Output is correct - L* = 40
33 Correct 73 ms 2392 KB Output is correct - L* = 40
34 Correct 72 ms 2436 KB Output is correct - L* = 40
35 Correct 72 ms 2460 KB Output is correct - L* = 40
36 Correct 75 ms 2856 KB Output is correct - L* = 40
37 Correct 72 ms 2496 KB Output is correct - L* = 40
38 Correct 74 ms 2444 KB Output is correct - L* = 40
39 Correct 78 ms 2532 KB Output is correct - L* = 40
40 Correct 76 ms 2556 KB Output is correct - L* = 40