Submission #578458

#	Time	Username	Problem	Language	Result	Execution time	Memory
578458		8e7	Flight to the Ford (BOI22_communication)	C++17	0 / 100	2 ms	292 KiB

communication

//Challenge: Accepted
#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...); }
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define maxc 31
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);

int se[16];
int str[4] = {0, 6, 9, 15};
int xo[7] = {1, 2, 4, 5, 8, 9, 10};
void init() {
	for (int i = 0;i < 4;i++) {
		for (int j = 0;j < 7;j++) {
			se[str[i] ^ xo[j]] |= 1<<i;
		}
	}
}

int getlen(vector<pii> t) {
	int ret = 0;
	for (auto p:t) ret += p.ss - p.ff + 1;
	return ret;
}
vector<vector<pii> > split(vector<pii> t) {
	int len = (getlen(t) + 3) / 4;	
	int cur = 0;
	vector<vector<pii> > ret;
	vector<pii> v;
	for (int i = 0;i < t.size();i++) {
		pii p = t[i];
		//debug("split", p.ff, p.ss);
		int l = p.ss - p.ff + 1;
		if (cur + l <= len) {
			v.push_back(p);
			cur += l;
			if (cur == len) {
				ret.push_back(v);
				cur = 0;
				v.clear();
			}
		} else {
			v.push_back({p.ff, p.ff + len - cur - 1});
			cur = 0;
			ret.push_back(v);
			v.clear();

			t[i].ff += len - cur;
			i--;
		}
	}
	if (v.size()) {
		ret.push_back(v);
		v.clear();
	}
	while (ret.size() < 4) ret.push_back(v);
	return ret;
}
int st = 1;
void encode(int N, int X) {
	if (st) {
		st = 0;
		init();
	}

	vector<pii> t;
	t.push_back({1, N});
	while (getlen(t) > 2) {
		debug("t");
		for (auto p:t) debug(p.ff, p.ss);
		debug();
		vector<vector<pii> > s = split(t);
		int p = 0, r = 0, id = 0;
		for (int i = 0;i < 4;i++) {
			for (auto j:s[i]) debug(j.ff, j.ss);
			debug();
			int mi = s[i][0].ff, ma = s[i].back().ss;	
			if (mi <= X && X <= ma) {
				id = i;
				p = str[i];
				break;
			}
		}
		debug(id);
		for (int i = 0;i < 4;i++) {
			r += (1<<i) * send((p >> i) & 1);
		}
		r = se[r];
		vector<pii> to = s[id];
		for (int i = 0;i < 4;i++) {
			if (i != id && ((r >> i) & 1)) {
				to.insert(to.end(), s[i].begin(), s[i].end());
			}
		}
		t = to;
	}
}

std::pair<int, int> decode(int N) {
	if (st) {
		st = 0;
		init();
	}

	vector<pii> t;
	t.push_back({1, N});
	while (getlen(t) > 2) {
		debug("t");
		for (auto p:t) debug(p.ff, p.ss);
		debug();

		vector<vector<pii> > s = split(t);
		int r = 0;	
		for (int i = 0;i < 4;i++) {
			r += (1<<i) * receive();
		}
		debug(r);
		r = se[r];
		vector<pii> to;
		for (int i = 0;i < 4;i++) {
			if (((r >> i) & 1)) {
				debug(i);
				to.insert(to.end(), s[i].begin(), s[i].end());
			}
		}
		t = to;
	}
    return {t[0].ff, t.back().ss};
}

Compilation message (stderr)

communication.cpp: In function 'std::vector<std::vector<std::pair<int, int> > > split(std::vector<std::pair<int, int> >)':
communication.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int i = 0;i < t.size();i++) {
      |                 ~~^~~~~~~~~~
communication.cpp: In function 'void encode(int, int)':
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
communication.cpp:84:3: note: in expansion of macro 'debug'
   84 |   debug("t");
      |   ^~~~~
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
communication.cpp:85:18: note: in expansion of macro 'debug'
   85 |   for (auto p:t) debug(p.ff, p.ss);
      |                  ^~~~~
communication.cpp:85:13: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   85 |   for (auto p:t) debug(p.ff, p.ss);
      |             ^
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
communication.cpp:86:3: note: in expansion of macro 'debug'
   86 |   debug();
      |   ^~~~~
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
communication.cpp:90:22: note: in expansion of macro 'debug'
   90 |    for (auto j:s[i]) debug(j.ff, j.ss);
      |                      ^~~~~
communication.cpp:90:14: warning: variable 'j' set but not used [-Wunused-but-set-variable]
   90 |    for (auto j:s[i]) debug(j.ff, j.ss);
      |              ^
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
communication.cpp:91:4: note: in expansion of macro 'debug'
   91 |    debug();
      |    ^~~~~
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
communication.cpp:99:3: note: in expansion of macro 'debug'
   99 |   debug(id);
      |   ^~~~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
communication.cpp:123:3: note: in expansion of macro 'debug'
  123 |   debug("t");
      |   ^~~~~
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
communication.cpp:124:18: note: in expansion of macro 'debug'
  124 |   for (auto p:t) debug(p.ff, p.ss);
      |                  ^~~~~
communication.cpp:124:13: warning: variable 'p' set but not used [-Wunused-but-set-variable]
  124 |   for (auto p:t) debug(p.ff, p.ss);
      |             ^
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
communication.cpp:125:3: note: in expansion of macro 'debug'
  125 |   debug();
      |   ^~~~~
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
communication.cpp:132:3: note: in expansion of macro 'debug'
  132 |   debug(r);
      |   ^~~~~
communication.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
communication.cpp:137:5: note: in expansion of macro 'debug'
  137 |     debug(i);
      |     ^~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85