Submission #1079876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079876		GusterGoose27	Bit Shift Registers (IOI21_registers)	C++17	0 / 100	11 ms	22108 KiB

registers

#include "registers.h"

#include <bits/stdc++.h>

using namespace std;

static const int id_move = 0;
static const int id_store = 1;
static const int id_and = 2;
static const int id_or = 3;
static const int id_xor = 4;
static const int id_not = 5;
static const int id_left = 6;
static const int id_right = 7;
static const int id_add = 8;

const int B = 2000;
const int MAXN = 1e5+5;

int ids[MAXN];
vector<int> nxt[MAXN];
vector<int> rev[MAXN];
int deg[MAXN];
bool vis[MAXN];
vector<int> topo;

struct op {
	vector<bool> v;
	int x, y;
	int tp = -1;
	op() {}
	op(vector<bool> v, int tp) : v(v), tp(tp) {}
	op(int x, int tp) : tp(), x(x) {} 
	op(int x, int y, int tp) : tp(tp), x(x), y(y) {}
	void append(int t) {
		x = ids[x];
		y = ids[y];
		t = ids[t];
		switch(tp) {
            case id_move:
                append_move(t, x);
                break;
            case id_store:
                append_store(t, v);
                break;
            case id_and:
                append_and(t, x, y);
                break;
            case id_or:
                append_or(t, x, y);
                break;
            case id_xor:
                append_xor(t, x, y);
                break;
            case id_not:
                append_not(t, x);
                break;
            case id_left:
                append_left(t, x, y);
                break;
            case id_right:
                append_right(t, x, y);
                break;
            case id_add:
                append_add(t, x, y);
                break;
            // case id_print:
            //     append_print(t);
            //     break;
            default:
                assert(false);
        } 
	}
};

op ops[MAXN];

int t = 1;
int n, k;

void make_edge(int x, int y) {
	nxt[x].push_back(y);
	rev[y].push_back(x);
	deg[x]++;
}

int make_move(int y) {
	make_edge(y, t);
	ops[t] = op(y, id_move);
	return t++;
}

int make_store(vector<bool> v) {
	// make_edge(y, t);
	ops[t] = op(v, id_store);
	return t++;
}

int make_and(int x, int y) {
	make_edge(x, t);
	make_edge(y, t);
	ops[t] = op(x, y, id_and);
	return t++;
}

int make_or(int x, int y) {
	make_edge(x, t);
	make_edge(y, t);
	ops[t] = op(x, y, id_or);
	return t++;
}

int make_xor(int x, int y) {
	make_edge(x, t);
	make_edge(y, t);
	ops[t] = op(x, y, id_xor);
	return t++;
}

int make_not(int x) {
	make_edge(x, t);
	// make_edge(y, t);
	ops[t] = op(x, id_not);
	return t++;
}

int make_left(int x, int y) {
	make_edge(x, t);
	make_edge(y, t);
	ops[t] = op(x, y, id_left);
	return t++;
}

int make_right(int x, int y) {
	make_edge(x, t);
	make_edge(y, t);
	ops[t] = op(x, y, id_right);
	return t++;
}

int make_add(int x, int y) {
	make_edge(x, t);
	make_edge(y, t);
	ops[t] = op(x, y, id_add);
	return t++;
}

int prefix_spread(int x, bool care) {
	for (int i = 0; (1<<i) < k; i++) {
		int y = make_right(x, (1<<i));
		if (care) {
			vector<bool> spec(B, 0);//.assign(B, 0);
			for (int u = 0; u < B; u += k) {
				for (int j = 0; j < k-(1<<i); j++) spec[u+j] = 1;
			}
			y = make_and(y, make_store(spec));
		}
		// append_print(x);
		// append_print(y);
		x = make_or(x, y);
	}
	return x;
}

int make_min(int x, int y, bool care) { // also free x and y
	int u = make_and(x, make_not(y));
	int v = make_and(y, make_not(x));
	u = make_and(u, make_not(prefix_spread(v, care)));
	u = prefix_spread(u, care);
	int xy = make_and(u, make_xor(x, y));
	return make_xor(x, xy);
}

void dfs(int cur) {
	topo.push_back(cur);
	vis[cur] = 1;
	for (int v: nxt[cur]) {
		if (!vis[v]) dfs(v);
	}
}

void construct_instructions(int s, int N, int K, int q) {
	n = N; k = K;
	assert(s == 0);
	int u = 0;
	// for (int i = 1; i < 100; i++) avail.insert(i);
	for (int b = 0; (1<<b)<n; b++) {
		u = make_min(u, make_right(u, k<<b), b>0);
	}
	for (int i = 0; i < t; i++) {
		if (!vis[i]) dfs(i);
	}
	reverse(topo.begin(), topo.end());
	set<int> avail;
	for (int i = 0; i < 100; i++) avail.insert(i);
	// set<int> waiting;
	for (int v: topo) {
		assert(!avail.empty());
		ids[v] = *avail.begin();
		avail.erase(ids[v]);
		// if (deg[v]) waiting.insert(v);
		for (int x: rev[v]) {
			deg[x]--;
			if (!deg[x]) {
				// waiting.erase(x);
				avail.insert(ids[x]);
			}
		}
	}
	append_move(0, ids[u]);
}

Compilation message (stderr)

registers.cpp: In constructor 'op::op(int, int)':
registers.cpp:30:6: warning: 'op::tp' will be initialized after [-Wreorder]
   30 |  int tp = -1;
      |      ^~
registers.cpp:29:6: warning:   'int op::x' [-Wreorder]
   29 |  int x, y;
      |      ^
registers.cpp:33:2: warning:   when initialized here [-Wreorder]
   33 |  op(int x, int tp) : tp(), x(x) {}
      |  ^~
registers.cpp: In constructor 'op::op(int, int, int)':
registers.cpp:30:6: warning: 'op::tp' will be initialized after [-Wreorder]
   30 |  int tp = -1;
      |      ^~
registers.cpp:29:6: warning:   'int op::x' [-Wreorder]
   29 |  int x, y;
      |      ^
registers.cpp:34:2: warning:   when initialized here [-Wreorder]
   34 |  op(int x, int y, int tp) : tp(tp), x(x), y(y) {}
      |  ^~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 25
• Subtask 5: 0 / 13
• Subtask 6: 0 / 29