Submission #1220327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220327		thangdz2k7	Saveit (IOI10_saveit)	C++20	100 / 100	48 ms	5696 KiB

encoder

#ifdef EVAL

#include "grader.h"
#include "encoder.h"

#endif

#include <bits/stdc++.h>

using namespace std;

namespace changes{

	#define Bit(x, i) ((x) >> (i) & 1)
	#define Mask(i) (1 << (i))

	const int block3 = 39;
	const int block2 = 62;
	const int LG = 10;

	long long p2[block2], p3[block3];

	void init(){
		p2[0] = 1;
		for (int i = 1; i < block2; ++ i)
			p2[i] = p2[i - 1] * 2;

		p3[0] = 1;
		for (int i = 1; i < block3; ++ i) 
			p3[i] = p3[i - 1] * 3;

	}

	long long fval3(vector <int> states){
		long long rt = 0;
		for (int i = 0; i < int(states.size()); ++ i) 
			rt += p3[i] * states[i];

		return rt;
	}

	vector <int> tval3(long long val, int num){
		vector <int> states(num);
		for (int i = 0; i < num; ++ i){
			states[i] = val % 3;
			val /= 3;
		}

		return states;
	}

	long long fval2(vector <int> states){
		long long rt = 0;
		for (int i = 0; i < int(states.size()); ++ i)
			rt += p2[i] * states[i];

		return rt;
	}

	vector <int> tval2(long long val, int num){
		vector <int> states(num);
		for (int i = 0; i < num; ++ i){
			states[i] = val % 2;
			val /= 2;
		}

		return states;
	}
}

using namespace changes;

#ifndef EVAL

void encode_bit(int b){
}

#endif

void encode(int nv, int nh, int ne, int *v1, int *v2){
	init();
	vector <vector <int>> adj(nv);

	for (int i = 0; i < ne; ++ i){
		adj[v1[i]].push_back(v2[i]);
		adj[v2[i]].push_back(v1[i]);
	}

	vector <int> fa(nv, -1);

	function <void(int)> dfs = [&](int u){
		for (int v : adj[u]) if (v != fa[u] && v && fa[v] == -1){
			fa[v] = u;
			dfs(v);
		}
	};

	dfs(0);

	for (int i = 1; i < nv; ++ i){
		for (int l = 0; l < LG; ++ l)
			encode_bit(Bit(fa[i], l));
	}

	for (int r = 0; r < nh; ++ r){
		vector <int> dist(nv, -1);
		dist[r] = 0;
		queue <int> qu;
		qu.push(r);

		while (qu.size()){
			int u = qu.front(); qu.pop();

			for (int v : adj[u]) if (dist[v] < 0){
				dist[v] = dist[u] + 1;
				qu.push(v);
			}
		}

		for (int i = 1; i < nv; i += block3){
			vector <int> tmp;
			for (int j = i; j < min(nv, i + block3); ++ j)
				tmp.push_back(dist[j] - dist[fa[j]] + 1);

			for (int b : tval2(fval3(tmp), block2)) encode_bit(b);
		}
	}
}

#ifndef EVAL

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n; cin >> n;
	cout << n / 2;

	return 0;
}

#endif

decoder

#ifdef EVAL

#include "grader.h"
#include "decoder.h"

#endif

#include <bits/stdc++.h>

using namespace std;

namespace changes{

	#define Bit(x, i) ((x) >> (i) & 1)
	#define Mask(i) (1 << (i))

	const int block3 = 39;
	const int block2 = 62;
	const int LG = 10;

	long long p2[block2], p3[block3];

	void init(){
		p2[0] = 1;
		for (int i = 1; i < block2; ++ i)
			p2[i] = p2[i - 1] * 2;

		p3[0] = 1;
		for (int i = 1; i < block3; ++ i) 
			p3[i] = p3[i - 1] * 3;

	}

	long long fval3(vector <int> states){
		long long rt = 0;
		for (int i = 0; i < int(states.size()); ++ i) 
			rt += p3[i] * states[i];

		return rt;
	}

	vector <int> tval3(long long val, int num){
		vector <int> states(num);
		for (int i = 0; i < num; ++ i){
			states[i] = val % 3;
			val /= 3;
		}

		return states;
	}

	long long fval2(vector <int> states){
		long long rt = 0;
		for (int i = 0; i < int(states.size()); ++ i)
			rt += p2[i] * states[i];

		return rt;
	}

	vector <int> tval2(long long val, int num){
		vector <int> states(num);
		for (int i = 0; i < num; ++ i){
			states[i] = val % 2;
			val /= 2;
		}

		return states;
	}
}

using namespace changes;

#ifndef EVAL

int decode_bit(){
	return 0;
}

void hops(int h, int c, int d){


}

#endif

void decode(int nv, int nh){
	init();
	vector <int> fa(nv, -1);
	vector <vector <int>> adj(nv);

	for (int i = 1; i < nv; ++ i){
		fa[i] = 0;
		for (int l = 0; l < LG; ++ l)
			if (decode_bit()) fa[i] |= Mask(l);

		adj[fa[i]].push_back(i);
	}

	for (int r = 0; r < nh; ++ r){
		vector <int> diff(nv);
		for (int i = 1; i < nv; i += block3){
			vector <int> tmp;
			for (int j = 0; j < block2; ++ j)
				tmp.push_back(decode_bit());

			vector <int> cur = tval3(fval2(tmp), min(block3, nv - i));
			for (int j = 0; j < min(block3, nv - i); ++ j) 
				diff[i + j] = cur[j] - 1;
		}

		vector <int> dist(nv);
		dist[0] = 0; int u = r;
		while (u){
			dist[0] -= diff[u];
			u = fa[u];
		}

		function <void(int)> dfs = [&](int u) {
			for (int v : adj[u]) {
				dist[v] = dist[u] + diff[v];
				dfs(v);
			}
		};

		dfs(0);

		for (int i = 0; i < nv; ++ i) 
			hops(r, i, dist[i]);
	}
}

#ifndef EVAL

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n; cin >> n;
	cout << n / 2;

	return 0;
}

#endif

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25