답안 #341468

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
341468 2020-12-29T19:33:30 Z rqi Broken Device (JOI17_broken_device) C++14
85 / 100
55 ms 3236 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 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";
}
#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){
      |           ^~~~~~~~~~
# 결과 실행 시간 메모리 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