Submission #341468

#	Time	Username	Problem	Language	Result	Execution time	Memory
341468		rqi	Broken Device (JOI17_broken_device)	C++14	85 / 100	55 ms	3236 KiB

Anna

#include "Annalib.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;

#define pb push_back

#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

static mt19937 rng((uint32_t)(13053)); 

static int N;
static vi perm;
static vi iperm;

static void genPerm(){
	perm = vi(N, 0);
	iperm = vi(N, 0);
	for(int i = 0; i < N; i++){
		perm[i] = i;
	}
	shuffle(all(perm), rng);
	for(int i = 0; i < N; i++){
		iperm[perm[i]] = i;
	}
}

static vi apply(vi a, vi dif){
	vi na;
	for(int i = 0; i < N; i++){
		na.pb(a[dif[i]]);
	}
	return na;
}

static vi to_ternary(ll a){
	vi b;
	while(a > 0){
		b.pb(a % 3);
		a/=3;
	}
	return b;
}

static ll from_ternary(vi b){
	ll a = 0;
	ll curt = 1;
	for(auto u: b){
		a+=curt*u;
		curt*=3;
	}
	return a;
}

void Anna(int _N, ll _X, int K, int P[]){
	N = _N;
	genPerm();

	vi res(N, 0);
	vi bad(N, 0);
	for(int i = 0; i < K; i++){
		bad[P[i]] = 1;
	}

	vi X = to_ternary(_X);

	bad = apply(bad, perm);

	int curbit = 0;
	for(int i = 0; i < N; i+=2){
		if(!bad[i] && !bad[i+1] && curbit < sz(X)){
			//put the information in
			if(X[curbit] == 0){
				res[i] = 0;
				res[i+1] = 1;
			}
			else if(X[curbit] == 1){
				res[i] = 1;
				res[i+1] = 0;
			}
			else if(X[curbit] == 2){
				res[i] = 1;
				res[i+1] = 1;
			}
			curbit++;
		}
	}

	res = apply(res, iperm);

	for(int i = 0; i < N; i++){
		Set(i, res[i]);
		//cout << res[i];
	}
	//cout << "\n";
}

Bruno

#include "Brunolib.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;

#define pb push_back

#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

static mt19937 rng((uint32_t)(13053)); 

static int N;
static vi perm;
static vi iperm;

static void genPerm(){
	perm = vi(N, 0);
	iperm = vi(N, 0);
	for(int i = 0; i < N; i++){
		perm[i] = i;
	}
	shuffle(all(perm), rng);
	for(int i = 0; i < N; i++){
		iperm[perm[i]] = i;
	}
}

static vi apply(vi a, vi dif){
	vi na;
	for(int i = 0; i < N; i++){
		na.pb(a[dif[i]]);
	}
	return na;
}

static vi to_ternary(ll a){
	vi b;
	while(a > 0){
		b.pb(a % 3);
		a/=3;
	}
	return b;
}

static ll from_ternary(vi b){
	ll a = 0;
	ll curt = 1;
	for(auto u: b){
		a+=curt*u;
		curt*=3;
	}
	return a;
}

ll Bruno(int _N, int A[]){
	N = _N;
	vi res;
	for(int i = 0; i < N; i++){
		res.pb(A[i]);
	}
	genPerm();
	res = apply(res, perm);
	vi X;
	for(int i = 0; i < N; i+=2){
		if(res[i] == 0 && res[i+1] == 0) continue;
		if(res[i] == 0 && res[i+1] == 1){
			X.pb(0);
		}
		else if(res[i] == 1 && res[i+1] == 0){
			X.pb(1);
		}
		else if(res[i] == 1 && res[i+1] == 1){
			X.pb(2);
		}
	}
	ll ans = from_ternary(X);
	//cout << ans << "\n";
	return ans;
}

Compilation message (stderr)

Anna.cpp:48:11: warning: 'll from_ternary(vi)' defined but not used [-Wunused-function]
   48 | static ll from_ternary(vi b){
      |           ^~~~~~~~~~~~

Bruno.cpp:39:11: warning: 'vi to_ternary(ll)' defined but not used [-Wunused-function]
   39 | static vi to_ternary(ll a){
      |           ^~~~~~~~~~

• Subtask 1: 85 / 100