Submission #341468

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
341468	2020-12-29T19:33:30 Z	rqi	Broken Device (JOI17_broken_device)	C++14	85 / 100	55 ms	3236 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	50 ms	2936 KB	Output is partially correct - L* = 37
2	Partially correct	52 ms	2936 KB	Output is partially correct - L* = 38
3	Partially correct	50 ms	3064 KB	Output is partially correct - L* = 39
4	Partially correct	55 ms	3096 KB	Output is partially correct - L* = 38
5	Partially correct	51 ms	3000 KB	Output is partially correct - L* = 38
6	Partially correct	50 ms	2744 KB	Output is partially correct - L* = 38
7	Partially correct	51 ms	2972 KB	Output is partially correct - L* = 37
8	Partially correct	52 ms	2744 KB	Output is partially correct - L* = 38
9	Partially correct	50 ms	3064 KB	Output is partially correct - L* = 39
10	Partially correct	50 ms	2744 KB	Output is partially correct - L* = 37
11	Partially correct	50 ms	2944 KB	Output is partially correct - L* = 38
12	Partially correct	52 ms	3020 KB	Output is partially correct - L* = 39
13	Partially correct	52 ms	2944 KB	Output is partially correct - L* = 38
14	Partially correct	51 ms	2868 KB	Output is partially correct - L* = 39
15	Partially correct	50 ms	2740 KB	Output is partially correct - L* = 39
16	Partially correct	50 ms	2992 KB	Output is partially correct - L* = 39
17	Partially correct	50 ms	2740 KB	Output is partially correct - L* = 38
18	Partially correct	51 ms	2740 KB	Output is partially correct - L* = 38
19	Partially correct	50 ms	2936 KB	Output is partially correct - L* = 38
20	Partially correct	50 ms	2936 KB	Output is partially correct - L* = 38
21	Partially correct	51 ms	2944 KB	Output is partially correct - L* = 38
22	Partially correct	50 ms	2740 KB	Output is partially correct - L* = 38
23	Partially correct	53 ms	2868 KB	Output is partially correct - L* = 38
24	Partially correct	51 ms	3236 KB	Output is partially correct - L* = 38
25	Partially correct	50 ms	2892 KB	Output is partially correct - L* = 38
26	Partially correct	51 ms	2944 KB	Output is partially correct - L* = 38
27	Partially correct	53 ms	2744 KB	Output is partially correct - L* = 38
28	Partially correct	50 ms	2936 KB	Output is partially correct - L* = 38
29	Partially correct	51 ms	2868 KB	Output is partially correct - L* = 39
30	Partially correct	50 ms	2936 KB	Output is partially correct - L* = 39
31	Partially correct	51 ms	2936 KB	Output is partially correct - L* = 38
32	Partially correct	50 ms	2744 KB	Output is partially correct - L* = 38
33	Partially correct	50 ms	2740 KB	Output is partially correct - L* = 38
34	Partially correct	52 ms	2936 KB	Output is partially correct - L* = 39
35	Partially correct	54 ms	2940 KB	Output is partially correct - L* = 38
36	Partially correct	50 ms	2936 KB	Output is partially correct - L* = 39
37	Partially correct	50 ms	2744 KB	Output is partially correct - L* = 38
38	Partially correct	51 ms	2988 KB	Output is partially correct - L* = 37
39	Partially correct	52 ms	2912 KB	Output is partially correct - L* = 38
40	Partially correct	50 ms	2976 KB	Output is partially correct - L* = 37