oj.uz

Submission #341559

# Submission time Handle Problem Language Result Execution time Memory
341559 2020-12-30T02:51:22 Z rqi Broken Device (JOI17_broken_device) C++14
100 / 100
 50 ms 3204 KB 
#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 offset;

static void genOffset(){
	for(int i = 0; i < 38; i++){
		offset.pb(rng() % 3);
	}
}

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_binary(ll a, int bitnum){
	vi b;
	for(int i = 0; i < bitnum; i++){
		b.pb(a % 2);
		a/=2;
	}
	return b;
}

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

static vi to_ternary(ll a, int bitnum = 38){
	vi b;
	for(int i = 0; i < bitnum; i++){
		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;
}

static vi to_sevary(ll a, int bitnum = 22){
	vi b;
	for(int i = 0; i < bitnum; i++){
		b.pb(a % 7);
		a/=7;
	}
	return b;
}

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

static vi res;
static vi bad;

void assignDoubBit(int pos, int val){
	if(val == 0){
		return;	//0 double bit means 0
	}
	if(bad[pos] == 0){
		res[pos] = 1;
	}
	else{
		assert(bad[pos+1] == 0);
		res[pos+1] = 1;
	}
}

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

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

	vi X = to_ternary(_X);
	assert(sz(X) == 38);

	//bad = apply(bad, perm);

	int fullbins = 0;
	for(int i = 0; i < N; i+=2){
		if(!bad[i] && !bad[i+1]) fullbins++;
	}

	if(fullbins >= 38){
		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++;
			}
		}
	}
	else{
		X = to_sevary(_X); //22 bits
		int curbit = 0;
		for(int i = 0; i+6-1 < 150; i+=6){
			if((bad[i] && bad[i+1]) || (bad[i+2] && bad[i+3]) || (bad[i+4] && bad[i+5]) || curbit >= sz(X)){
				continue;
			}
			vi Y = to_binary(X[curbit]+1, 3);
			for(int j = 0; j < 3; j++){
				assignDoubBit(i+2*j, Y[j]);
			}
			curbit++;
		}

		//count number of nonzero double bits. If ==38, make last possible nonzero
		int doubbits = 0;
		for(int i = 0; i < 150; i+=2){
			if(res[i] == 1 || res[i+1] == 1) doubbits++;
		}

		if(doubbits == 38){
			for(int i = 148; i >= 0; i--){
				if((!bad[i] || !bad[i+1]) && (res[i] == 0 && res[i+1] == 0)){
					if(!bad[i]){
						res[i] = 1;
					}
					if(!bad[i+1]){
						res[i+1] = 1;
					}
					break;
				}
			}
		}
	}

	

	//res = apply(res, iperm);

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

#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 offset;

static void genOffset(){
	for(int i = 0; i < 38; i++){
		offset.pb(rng() % 3);
	}
}

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_binary(ll a, int bitnum){
	vi b;
	for(int i = 0; i < bitnum; i++){
		b.pb(a % 2);
		a/=2;
	}
	return b;
}

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

static vi to_ternary(ll a, int bitnum = 38){
	vi b;
	for(int i = 0; i < bitnum; i++){
		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;
}

static vi to_sevary(ll a, int bitnum = 22){
	vi b;
	for(int i = 0; i < bitnum; i++){
		b.pb(a % 7);
		a/=7;
	}
	return b;
}

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

ll Bruno(int _N, int A[]){
	N = _N;
	vi res;
	for(int i = 0; i < N; i++){
		res.pb(A[i]);
	}
	// genPerm();
	// genOffset();
	// res = apply(res, perm);

	int doubbits = 0;
	for(int i = 0; i < 150; i+=2){
		if(res[i] == 1 || res[i+1] == 1) doubbits++;
	}

	
	ll ans;

	if(doubbits == 38){
		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);
			}
		}
		assert(sz(X) == 38);
		ans = from_ternary(X);
	}
	else{
		vi X;
		for(int i = 0; i < 150; i+=6){
			if(sz(X) >= 22) break;
			vi Y;
			for(int j = i; j < i+6; j+=2){
				if(res[j] == 0 && res[j+1] == 0){
					Y.pb(0);
				}
				else{
					Y.pb(1);
				}
			}
			int val = from_binary(Y);
			assert(0 <= val && val <= 7);
			if(val >= 1) X.pb(val-1);
		}
		assert(sz(X) == 22);
		ans = from_sevary(X);
		// cout << ans << "\n";
	}
	
	
	//cout << ans << "\n";
	return ans;
}

Compilation message

Anna.cpp:94:11: warning: 'll from_sevary(vi)' defined but not used [-Wunused-function]
   94 | static ll from_sevary(vi b){
      |           ^~~~~~~~~~~
Anna.cpp:75:11: warning: 'll from_ternary(vi)' defined but not used [-Wunused-function]
   75 | static ll from_ternary(vi b){
      |           ^~~~~~~~~~~~
Anna.cpp:56:11: warning: 'll from_binary(vi)' defined but not used [-Wunused-function]
   56 | static ll from_binary(vi b){
      |           ^~~~~~~~~~~
Anna.cpp:39:11: warning: 'vi apply(vi, vi)' defined but not used [-Wunused-function]
   39 | static vi apply(vi a, vi dif){
      |           ^~~~~
Anna.cpp:33:13: warning: 'void genOffset()' defined but not used [-Wunused-function]
   33 | static void genOffset(){
      |             ^~~~~~~~~
Anna.cpp:19:13: warning: 'void genPerm()' defined but not used [-Wunused-function]
   19 | static void genPerm(){
      |             ^~~~~~~

Bruno.cpp:85:11: warning: 'vi to_sevary(ll, int)' defined but not used [-Wunused-function]
   85 | static vi to_sevary(ll a, int bitnum = 22){
      |           ^~~~~~~~~
Bruno.cpp:66:11: warning: 'vi to_ternary(ll, int)' defined but not used [-Wunused-function]
   66 | static vi to_ternary(ll a, int bitnum = 38){
      |           ^~~~~~~~~~
Bruno.cpp:47:11: warning: 'vi to_binary(ll, int)' defined but not used [-Wunused-function]
   47 | static vi to_binary(ll a, int bitnum){
      |           ^~~~~~~~~
Bruno.cpp:39:11: warning: 'vi apply(vi, vi)' defined but not used [-Wunused-function]
   39 | static vi apply(vi a, vi dif){
      |           ^~~~~
Bruno.cpp:33:13: warning: 'void genOffset()' defined but not used [-Wunused-function]
   33 | static void genOffset(){
      |             ^~~~~~~~~
Bruno.cpp:19:13: warning: 'void genPerm()' defined but not used [-Wunused-function]
   19 | static void genPerm(){
      |             ^~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2948 KB Output is correct - L* = 40
2 Correct 47 ms 2744 KB Output is correct - L* = 40
3 Correct 45 ms 3100 KB Output is correct - L* = 40
4 Correct 45 ms 2940 KB Output is correct - L* = 40
5 Correct 48 ms 2744 KB Output is correct - L* = 40
6 Correct 45 ms 2872 KB Output is correct - L* = 40
7 Correct 45 ms 2940 KB Output is correct - L* = 40
8 Correct 47 ms 3068 KB Output is correct - L* = 40
9 Correct 49 ms 2744 KB Output is correct - L* = 40
10 Correct 45 ms 2940 KB Output is correct - L* = 40
11 Correct 46 ms 2948 KB Output is correct - L* = 40
12 Correct 45 ms 2872 KB Output is correct - L* = 40
13 Correct 46 ms 2796 KB Output is correct - L* = 40
14 Correct 46 ms 2740 KB Output is correct - L* = 40
15 Correct 45 ms 2740 KB Output is correct - L* = 40
16 Correct 45 ms 2940 KB Output is correct - L* = 40
17 Correct 47 ms 2808 KB Output is correct - L* = 40
18 Correct 46 ms 2868 KB Output is correct - L* = 40
19 Correct 45 ms 2744 KB Output is correct - L* = 40
20 Correct 45 ms 2948 KB Output is correct - L* = 40
21 Correct 45 ms 2740 KB Output is correct - L* = 40
22 Correct 45 ms 2940 KB Output is correct - L* = 40
23 Correct 45 ms 2940 KB Output is correct - L* = 40
24 Correct 48 ms 3020 KB Output is correct - L* = 40
25 Correct 45 ms 2744 KB Output is correct - L* = 40
26 Correct 46 ms 2892 KB Output is correct - L* = 40
27 Correct 45 ms 2872 KB Output is correct - L* = 40
28 Correct 45 ms 2940 KB Output is correct - L* = 40
29 Correct 47 ms 2888 KB Output is correct - L* = 40
30 Correct 45 ms 2892 KB Output is correct - L* = 40
31 Correct 45 ms 2740 KB Output is correct - L* = 40
32 Correct 45 ms 2948 KB Output is correct - L* = 40
33 Correct 45 ms 2740 KB Output is correct - L* = 40
34 Correct 45 ms 2740 KB Output is correct - L* = 40
35 Correct 46 ms 2872 KB Output is correct - L* = 40
36 Correct 45 ms 2872 KB Output is correct - L* = 40
37 Correct 47 ms 3204 KB Output is correct - L* = 40
38 Correct 50 ms 2868 KB Output is correct - L* = 40
39 Correct 45 ms 2948 KB Output is correct - L* = 40
40 Correct 45 ms 3000 KB Output is correct - L* = 40