Submission #804626

#	Time	Username	Problem	Language	Result	Execution time	Memory
804626		sentheta	Broken Device (JOI17_broken_device)	C++17	100 / 100	81 ms	2856 KiB

Anna

#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);
}

Bruno

#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 / 100