Submission #207623

#	Time	Username	Problem	Language	Result	Execution time	Memory
207623		autumn_eel	Broken Device (JOI17_broken_device)	C++14	100 / 100	1478 ms	3568 KiB

Anna

#include "Annalib.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;

bool b[160],d[160];
bool used[160];

void Anna(int N,ll X,int K,int P[]){
	static mt19937 mt(314159);
	uniform_int_distribution<>dist(0,N-1);
	memset(b,0,sizeof(b));
	memset(d,0,sizeof(d));
	memset(used,0,sizeof(used));
	rep(i,K){
		b[P[i]]=1;
	}
	rep(loop,N/2){
		int i,j;
		do{
			i=dist(mt);
			j=dist(mt);
		}while(i==j||used[i]||used[j]);
		used[i]=used[j]=true;
		int e=X%3;
		if((e==0&&!b[j])||(e==1&&!b[i])||(e==2&&!b[i]&&!b[j])){
			if(e==0)d[i]=0,d[j]=1;
			if(e==1)d[i]=1,d[j]=0;
			if(e==2)d[i]=1,d[j]=1;
			X/=3;
		}
	}
	rep(i,N)Set(i,d[i]);
}

Bruno

#include "Brunolib.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;

ll Bruno(int N,int A[]){
	static mt19937 mt(314159);
	uniform_int_distribution<>dist(0,N-1);
	bool used[160]{};
	ll ans=0,x=1;
	rep(loop,N/2){
		int i,j;
		do{
			i=dist(mt);
			j=dist(mt);
		}while(i==j||used[i]||used[j]);
		used[i]=used[j]=true;
		if(A[i]||A[j]){
			ans+=(A[i]*2+A[j]-1)*x;
			x*=3;
		}
	}
	return ans;
}

• Subtask 1: 100 / 100