oj.uz

Submission #946070

# Submission time Handle Problem Language Result Execution time Memory
946070 2024-03-14T09:56:06 Z PenguinsAreCute Vision Program (IOI19_vision) C++17
0 / 100
 10 ms 1748 KB 
#include "vision.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
// i dont think this is the intended solution...

// adds 2 bits. uses 2 instructions and 4 inputs.
vector<int> half_adder(int a, int b) {
	return {add_xor({a,b}),add_and({a,b})};
}
// adds 3 bits. uses 5 instructions and 12 inputs.
vector<int> full_adder(int a, int b, int c) {
	return {add_xor({a,b,c}), add_or({add_and({a,b}),add_and({b,c}),add_and({a,c})})};
}

// adds 2 9-bit integers. uses 42 instructions and 100 inputs.
vector<int> ninebit_add(vector<int> a, vector<int> b) {
	vector<int> ans(9);
	auto v = half_adder(a[0],b[0]);
	int carry = v[1]; ans[0] = v[0];
	for(int i=1;i<9;i++) {
		v = full_adder(a[i],b[i],carry);
		carry = v[1]; ans[i] = v[0];
	}
	return ans;
}
void construct_network(int H, int W, int K) {
	vector<int> x1(9), x2(9), y1(9), y2(9);
	int arr[max(H,W)], arr1[max(H,W)];
	for(int i=0;i<H;i++) {
		vector<int> v;
		for(int j=0;j<W;j++) v.push_back(i*W+j);
		arr[i] = add_or(v);
	}
	arr1[0] = arr[0];
	for(int i=1;i<H;i++) arr1[i] = add_or({arr1[i-1],arr[i]});
	for(int i=0;i<9;i++) {
		vector<int> v;
		for(int j=1;j<H;j++) if((-j)&(1<<i)) v.push_back(add_and({arr1[j],add_not(arr1[j-1])}));
		if(v.size()) x1[i] = add_or(v);
		else x1[i] = add_xor({0,0});
	}
	arr1[H-1] = arr[H-1];
	for(int i=H-1;i--;) arr1[i] = add_or({arr1[i+1],arr[i]});
	for(int i=0;i<9;i++) {
		vector<int> v;
		if((H-1)&(1<<i)) v.push_back(arr[H-1]);
		for(int j=0;j<H-1;j++) if(j&(1<<i)) v.push_back(add_and({arr[j],add_not(arr[j+1])}));
		if(v.size()) x2[i] = add_or(v);
		else x2[i] = add_xor({0,0});
	}

	for(int i=0;i<W;i++) {
		vector<int> v;
		for(int j=0;j<H;j++) v.push_back(j*W+i);
		arr[i] = add_or(v);
	}
	arr1[0] = arr[0];
	for(int i=1;i<W;i++) arr1[i] = add_or({arr1[i-1],arr[i]});
	for(int i=0;i<9;i++) {
		vector<int> v;
		for(int j=1;j<W;j++) if((-j)&(1<<i)) v.push_back(add_and({arr1[j],add_not(arr1[j-1])}));
		if(v.size()) y1[i] = add_or(v);
		else y2[i] = add_xor({0,0});
	}
	arr1[W-1] = arr[W-1];
	for(int i=W-1;i--;) arr1[i] = add_or({arr1[i+1],arr[i]});
	for(int i=0;i<9;i++) {
		vector<int> v;
		if((W-1)&(1<<i)) v.push_back(arr[W-1]);
		for(int j=0;j<W-1;j++) if(j&(1<<i)) v.push_back(add_and({arr[j],add_not(arr[j+1])}));
		if(v.size()) y2[i] = add_or(v);
		else y2[i] = add_xor({0,0});
	}
	vector<int> dist = ninebit_add(ninebit_add(x1,y1),ninebit_add(x2,y2));
	vector<int> v;
	for(int i=0;i<9;i++) v.push_back((K&(1<<i))?dist[i]:add_not(dist[i]));
	add_and(v);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB on inputs (0, 0), (1, 0), expected 1, but computed 0
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB on inputs (0, 0), (1, 0), expected 1, but computed 0
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB on inputs (0, 0), (1, 0), expected 1, but computed 0
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB on inputs (0, 0), (1, 0), expected 1, but computed 0
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 728 KB Output is correct
2 Incorrect 2 ms 728 KB on inputs (0, 4), (0, 99), expected 0, but computed 1
3 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 3 ms 856 KB Output is correct
12 Correct 3 ms 784 KB Output is correct
13 Correct 2 ms 728 KB Output is correct
14 Correct 2 ms 736 KB Output is correct
15 Correct 2 ms 728 KB Output is correct
16 Correct 2 ms 728 KB Output is correct
17 Incorrect 2 ms 728 KB on inputs (0, 0), (1, 0), expected 1, but computed 0
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1748 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 3 ms 856 KB Output is correct
5 Correct 2 ms 728 KB Output is correct
6 Incorrect 2 ms 728 KB on inputs (0, 0), (1, 0), expected 1, but computed 0
7 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB on inputs (0, 0), (1, 0), expected 1, but computed 0
4 Halted 0 ms 0 KB -