oj.uz

답안 #761522

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
761522 2023-06-19T22:07:04 Z radoslav11 Vision Program (IOI19_vision) C++17
0 / 100
 8 ms 1328 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include "vision.h"

using namespace std;

vector<int> only_first_set(vector<int> nums) {
	vector<int> ans, pref;
	pref.push_back(nums[0]);
	ans.push_back(nums[0]);
	for(int i = 1; i < (int)nums.size(); i++) {
		pref.push_back(add_or({pref.back(), nums[i]}));
		ans.push_back(add_and({add_not(pref[i - 1]), nums[i]}));
	}

	return ans;
}

vector<int> to_binary(vector<int> unary) {
	vector<int> ans;
	for(int i = 0; ; i++) {
		vector<int> Ns;
		for(int j = 0; j < (int)unary.size(); j++) {
			if((j >> i) & 1) {
				Ns.push_back(unary[j]);
			}
		}

		if(Ns.empty()) {
			break;
		} 		

		ans.push_back(add_or(Ns));
	}

	return ans;
}

vector<int> binary_add(vector<int> a, vector<int> b) {
	vector<int> ans;
	int carry = -1;
	for(int i = 0; i < (int)a.size() || i < (int)b.size(); i++) {
		vector<int> Ns;
		if(i < (int)a.size()) {
			Ns.push_back(a[i]);
		}
		if(i < (int)b.size()) {
			Ns.push_back(b[i]);
		}
		if(carry != -1) {
			Ns.push_back(carry);
		}

		ans.push_back(add_xor(Ns));

		// 2 set for carry
		vector<int> Ns2;
		for(int p1 = 0; p1 < (int)Ns.size(); p1++) {
			for(int p2 = p1 + 1; p2 < (int)Ns.size(); p2++) {
				Ns2.push_back(add_and({Ns[p1], Ns[p2]}));
			}
		}

		carry = add_or(Ns2); 
	}
	
	ans.push_back(carry);
	return ans;
}

void construct_network(int H, int W, int K) {
    K = H + W - K - 2;

    vector<int> nums_unary[4];
    for(int i = 0; i < H; i++) {
        vector<int> Ns;
        for(int j = 0; j < W; j++) {
            Ns.push_back(i * W + j);
        }

        nums_unary[0].push_back(add_or(Ns));
    }
	nums_unary[1] = nums_unary[0];
	reverse(nums_unary[1].begin(), nums_unary[1].end());

    for(int j = 0; j < W; j++) {
        vector<int> Ns;
        for(int i = 0; i < H; i++) {
            Ns.push_back(i * W + j);
        }

        nums_unary[2].push_back(add_or(Ns));
    }
	nums_unary[3] = nums_unary[2];
	reverse(nums_unary[3].begin(), nums_unary[3].end());

	for(int i = 0; i < 4; i++) {
		nums_unary[i] = only_first_set(nums_unary[i]);
		nums_unary[i] = to_binary(nums_unary[i]);
	}

	vector<int> ans = nums_unary[0];
	for(int i = 1; i < 4; i++) {
		ans = binary_add(ans, nums_unary[i]);
	}
	
	vector<int> Ns_check;
	for(int i = 0; i < (int)ans.size(); i++) {
		if((K >> i) & 1) {
			Ns_check.push_back(ans[i]);
		} else {
			Ns_check.push_back(add_not(ans[i]));
		}
	}

	add_and(Ns_check);
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 428 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 2 ms 424 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Incorrect 1 ms 340 KB WA in grader: Invalid index
14 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1328 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Incorrect 1 ms 296 KB WA in grader: Invalid index
6 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -