제출 #1079908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1079908		GusterGoose27	레지스터 (IOI21_registers)	C++17	21 / 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;
	bool pr;
	int tp = -1;
	int x, y;
	op() {}
	op(vector<bool> v, int tp, bool pr = 0) : v(v), tp(tp), pr(pr) {}
	op(int x, int tp, bool pr = 0) : tp(tp), x(x), pr(pr) {} 
	op(int x, int y, int tp, bool pr = 0) : tp(tp), x(x), y(y), pr(pr) {}
	void append(int t) {
		x = ids[x];
		if (tp != id_left && tp != id_right) 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);
        } 
        // if (pr) append_print(t);
	}
};

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, bool pr = 0) {
	// assert(false);
	make_edge(y, t);
	ops[t] = op(y, id_move, pr);
	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, bool pr = 0) {
	make_edge(x, t);
	make_edge(y, t);
	ops[t] = op(x, y, id_or, pr);
	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, bool pr = 0) {
	make_edge(x, t);
	// make_edge(y, t);
	ops[t] = op(x, y, id_right, pr);
	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) {
	// make_move(x, 1);
	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);
		// make_move(y, 1);
		x = make_or(x, y, 1);
	}
	return x;
}

int make_min(int x, int y, bool care) { // also free x and y
	// make_move(x, 1);
	// make_move(y, 1);
	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);
	// append_print(0);
	// make_not(0);
	// make_move(0, 1);
	int u = 0;
	// for (int i = 1; i < 100; i++) avail.insert(i);
	for (int b = 0; (1<<b)<n; b++) {
		// cerr << (k<<b) << '\n';
		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 = 0; v < t; v++) {
		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]);
			}
		}
		if (v) {
			// cerr << ops[v].tp << '\n';
			// cerr << ops[v].x << ' ' << ops[v].y << '\n';
			ops[v].append(v == t-1 ? 0 : v);
		}
	}
	// append_move(0, ids[u]);
}

컴파일 시 표준 에러 (stderr) 메시지

registers.cpp: In constructor 'op::op(std::vector<bool>, int, bool)':
registers.cpp:30:6: warning: 'op::tp' will be initialized after [-Wreorder]
   30 |  int tp = -1;
      |      ^~
registers.cpp:29:7: warning:   'bool op::pr' [-Wreorder]
   29 |  bool pr;
      |       ^~
registers.cpp:33:2: warning:   when initialized here [-Wreorder]
   33 |  op(vector<bool> v, int tp, bool pr = 0) : v(v), tp(tp), pr(pr) {}
      |  ^~
registers.cpp: In constructor 'op::op(int, int, bool)':
registers.cpp:31:6: warning: 'op::x' will be initialized after [-Wreorder]
   31 |  int x, y;
      |      ^
registers.cpp:29:7: warning:   'bool op::pr' [-Wreorder]
   29 |  bool pr;
      |       ^~
registers.cpp:34:2: warning:   when initialized here [-Wreorder]
   34 |  op(int x, int tp, bool pr = 0) : tp(tp), x(x), pr(pr) {}
      |  ^~
registers.cpp: In constructor 'op::op(int, int, int, bool)':
registers.cpp:31:9: warning: 'op::y' will be initialized after [-Wreorder]
   31 |  int x, y;
      |         ^
registers.cpp:29:7: warning:   'bool op::pr' [-Wreorder]
   29 |  bool pr;
      |       ^~
registers.cpp:35:2: warning:   when initialized here [-Wreorder]
   35 |  op(int x, int y, int tp, bool pr = 0) : tp(tp), x(x), y(y), pr(pr) {}
      |  ^~

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