oj.uz

답안 #1079892

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1079892 2024-08-29T03:06:41 Z GusterGoose27 레지스터 (IOI21_registers) C++17
0 / 100
 11 ms 22108 KB 
#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 tp = -1;
	int x, y;
	op() {}
	op(vector<bool> v, int tp) : v(v), tp(tp) {}
	op(int x, int tp) : 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);
        } 
        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) {
	assert(false);
	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);
	append_print(0);
	// make_not(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 = 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';
			ops[v].append(v);
		}
	}
	append_move(0, ids[u]);
}

Subtask #1
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 11100 KB Incorrect min value
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 11100 KB Incorrect min value
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 11100 KB Incorrect min value
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 11100 KB Wrong answer detected in grader
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 22108 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 22108 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -