Submission #1229648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229648		PenguinsAreCute	Broken Device (JOI17_broken_device)	C++17	81 / 100	38 ms	1596 KiB

Anna

#include "Annalib.h"
#include <bits/stdc++.h>
using namespace std;
void Anna( int N, long long X, int K, int P[] ) {
	int perm[N];
	iota(perm,perm+N,0);
	mt19937 rng(42069);
	shuffle(perm,perm+N,rng);
	X ^= (rng() & ((1LL << 60) - 1));
	int inv[N];
	for(int i=0;i<N;i++)
		inv[perm[i]] = i;
	bool val[N];
	memset(val,1,sizeof(val));
	for(int i=0;i<K;i++)
		val[inv[P[i]]] = 0;
	int cnt = 0;
	for(int i=0;i<N;) {
		if(i <= N - 4 && val[i] && (val[i+1] || !(X&(1LL<<cnt))) && (val[i+2] || !(X&(2LL<<cnt))) && (val[i+3] || !(X&(4LL<<cnt)))) {
			Set(perm[i],1);
			Set(perm[i+1],!!(X&(1LL<<(cnt++))));
			Set(perm[i+2],!!(X&(1LL<<(cnt++))));
			Set(perm[i+3],!!(X&(1LL<<(cnt++))));
			i += 4;
		} else
			Set(perm[i++],0);
	}
}

Bruno

#include "Brunolib.h"
#include <bits/stdc++.h>
using namespace std;
long long Bruno( int N, int A[] ){
	int perm[N];
	iota(perm,perm+N,0);
	mt19937 rng(42069);
	shuffle(perm,perm+N,rng);
	long long X = 0;
	int cnt = 0;
	for(int i=0;i<N;) {
		if(A[perm[i]]) {
			X |= A[perm[i+1]] * (1LL << (cnt++));
			X |= A[perm[i+2]] * (1LL << (cnt++));
			X |= A[perm[i+3]] * (1LL << (cnt++));
			i += 4;
		} else
			i++;
	}
	X ^= (rng() & ((1LL << 60) - 1));
	return X;
}

• Subtask 1: 81 / 100