Submission #366591

#	Time	Username	Problem	Language	Result	Execution time	Memory
366591		kostia244	Saveit (IOI10_saveit)	C++17	100 / 100	823 ms	20716 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
using namespace std;
namespace {
const int N = 1585;
const int SZ = 1 + (N*32)/30;
const uint ful = (1u<<30)-1;
struct big_int {
	uint a[SZ];
	big_int() {
		memset(a, 0, sizeof a);
	}
	void triple() {
		for(int i = 0; i < SZ; i++) a[i] *= 3;
		for(int i = 0; i+1 < SZ; i++) {
			a[i+1] += a[i]>>30;
			a[i] &= ful;
		}
	}
	void add(uint x) {
		int co = x;
		for(int i = 0; co;) {
			a[i] += co;
			co = a[i]>>30;
			a[i] &= ful;
		}
	}
	friend big_int operator+(big_int x, const big_int &y) {
		uint co = 0;
		for(int i = 0; i < SZ; i++) {
			x.a[i] += y.a[i]+co;
			co = x.a[i]>>30;
			x.a[i] &= ful;
		}
		return x;
	}
	friend bool operator<=(const big_int &a, const big_int &b) {
		int pos = SZ-1;
		while(pos >= 0 && a.a[pos] == b.a[pos]) pos--;
		return pos == -1 || a.a[pos] <= b.a[pos];
	}
	void send() {
		for(int i = 0; i < N; i++) {
			int val = a[i/30];
			val >>= i%30;
			encode_bit(val&1);
		}
	}
	void get() {
		for(int i = 0; i < N; i++) {
			int val = decode_bit();
			val <<= i%30;
			a[i/30] |= val;
		}
	}
	void print() {
		for(int i = 0; i < 30; i++) cout << ((a[0]>>i)&1);cout << endl;
	}
};
int n, par[N];
vector<int> g[N];
template<int build_tree>
void bfs(int v) {
	vector<int> dist(n+1, -1);
	queue<int> q;
	auto enq = [&](int v, int d, int P) {
		if(dist[v] != -1) return;
		dist[v] = d;
		if(build_tree) par[v] = P;
		q.push(v);
	};
	enq(v, 0, -1);
	while(!q.empty()) {
		int v = q.front();q.pop();
		for(auto i : g[v]) enq(i, dist[v]+1, v);
	}
	//for(int i = 0; i < n; i++) cout << dist[i] << " "; cout << endl;
	if(build_tree) {
		for(int i = 1; i < n; i++)
			for(int j = 0; j < 10; j++)
				encode_bit((par[i]>>j)&1);
	} else {
		for(int i = 0; i < 10; i++) encode_bit((dist[0]>>i)&1);
		big_int res;
		for(int i = 1; i < n; i++) {
			res.triple();
			res.add(1 + dist[i] - dist[par[i]]);
			//cout << v << " | " << i << " | " << 1 + dist[i] - dist[par[i]] << " res " << dist[i] << endl;
		}
		//cout << v << " res " << res.a[0] << endl;
		res.send();
	}
}
};
void encode(int V, int H, int E, int *v1, int *v2){
	n = V;
	for(int i = 0; i < E; i++) g[v1[i]].push_back(v2[i]);
	for(int i = 0; i < E; i++) g[v2[i]].push_back(v1[i]);
	bfs<1>(0);
	for(int i = 1; i < H; i++) bfs<0>(i);
	return;
}

decoder

#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>
using namespace std;
namespace {
const int N = 1585;
const int SZ = 1 + (N*32)/30;
const uint ful = (1u<<30)-1;
struct big_int {
	uint a[SZ];
	big_int() {
		memset(a, 0, sizeof a);
	}
	void triple() {
		for(int i = 0; i < SZ; i++) a[i] *= 3;
		for(int i = 0; i+1 < SZ; i++) {
			a[i+1] += a[i]>>30;
			a[i] &= ful;
		}
	}
	void add(uint x) {
		int co = x;
		for(int i = 0; co;) {
			a[i] += co;
			co = a[i]>>30;
			a[i] &= ful;
		}
	}
	friend big_int operator+(big_int x, const big_int &y) {
		uint co = 0;
		for(int i = 0; i < SZ; i++) {
			x.a[i] += y.a[i]+co;
			co = x.a[i]>>30;
			x.a[i] &= ful;
		}
		return x;
	}
	friend bool operator<=(const big_int &a, const big_int &b) {
		int pos = SZ-1;
		while(pos >= 0 && a.a[pos] == b.a[pos]) pos--;
		return pos == -1 || a.a[pos] <= b.a[pos];
	}
	void send() {
		for(int i = 0; i < N; i++) {
			int val = a[i/30];
			val >>= i%30;
			encode_bit(val&1);
		}
	}
	void get() {
		for(int i = 0; i < N; i++) {
			int val = decode_bit();
			val <<= i%30;
			a[i/30] |= val;
		}
	}
	void print() {
		for(int i = 0; i < 30; i++) cout << ((a[0]>>i)&1);cout << endl;
	}
};
int n, h, d21[N], par[N];
vector<int> g[N], ord;
void dfs(int v) {
	ord.push_back(v);
	for(int i : g[v]) dfs(i);
}
big_int pws[N];
}
void decode(int nv, int nh) {
	n = nv;
	h = nh;
	d21[0] = 0;
	for(int i = 1; i < n; i++) {
		for(int j = 0; j < 10; j++) {
			par[i] |= decode_bit()<<j;
		}
		g[par[i]].push_back(i);
	}
	dfs(0);
	//cout << "pT2\n";
	for(auto i : ord) if(i) d21[i] = d21[par[i]] + 1;
	for(int i = 0; i < n; i++) hops(0, i, d21[i]);
	pws[0].add(1);
	for(int i = 1; i < n; i++) pws[i] = pws[i-1], pws[i].triple();
	for(int hl = 1; hl < h; hl++) {
		memset(d21, 0, sizeof d21);
		for(int j = 0; j < 10; j++) d21[0] |= decode_bit()<<j;
		big_int dif;
		//cout << dif.a[0] << " - " << dif.a[1] << " - " << dif.a[2] << " - " << dif.a[3] << endl;
		dif.get();
		//cout << hl << " == " << dif.a[0] << endl;
		//cout << dif.a[0] << " - " << dif.a[1] << " - " << dif.a[2] << " - " << dif.a[3] << endl;
		big_int cur;
		for(int i = 1; i < n; i++) {
			int CCC = 0;
			big_int &cp = pws[n-i-1], nxt;
			//cout << cur.a[0] << " " << cp.a[0] << " " << dif.a[0] << endl;
			while(nxt = cur+cp, nxt <= dif) {
				cur = nxt;
				//cout << "inc\n";
				d21[i]++;
			}
			//cout << cur.a[0] << endl;
			//cout << hl << " : " << i << " : " << d21[i] << endl;
		}
		for(auto i : ord) if(i) {
			d21[i] -= 1;
			d21[i] += d21[par[i]];
			//cout << hl << " " << i << " res " << d21[i] << endl;
		}
		for(int i = 0; i < n; i++) hops(hl, i, d21[i]);
	}
}

Compilation message (stderr)

encoder.cpp: In member function 'void {anonymous}::big_int::print()':
encoder.cpp:58:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   58 |   for(int i = 0; i < 30; i++) cout << ((a[0]>>i)&1);cout << endl;
      |   ^~~
encoder.cpp:58:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   58 |   for(int i = 0; i < 30; i++) cout << ((a[0]>>i)&1);cout << endl;
      |                                                     ^~~~

decoder.cpp: In member function 'void {anonymous}::big_int::print()':
decoder.cpp:58:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   58 |   for(int i = 0; i < 30; i++) cout << ((a[0]>>i)&1);cout << endl;
      |   ^~~
decoder.cpp:58:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   58 |   for(int i = 0; i < 30; i++) cout << ((a[0]>>i)&1);cout << endl;
      |                                                     ^~~~
decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:95:8: warning: unused variable 'CCC' [-Wunused-variable]
   95 |    int CCC = 0;
      |        ^~~

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