답안 #991550

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
991550 2024-06-02T12:11:44 Z SanguineChameleon 마술쇼 (APIO24_show) C++17
컴파일 오류
0 ms 0 KB
#include "Alice.h"
#include <bits/stdc++.h>
using namespace std;

namespace alice_rng {
	unsigned long long state = 88172645463325252LL;

	long long rand_bits(int k) {
		state ^= (state << 13);
		state ^= (state >> 7);
		state ^= (state << 17);
		return (state & ((1LL << k) - 1));
	}

	long long rand_int(long long l, long long r) {
		long long d = r - l;
		int k = 0;
		while ((1LL << k) <= d) {
			k++;
		}
		while (true) {
			long long x = rand_bits(k);
			if (x <= d) {
				return l + x;
			}
		}
	}

	template <typename T>
	void shuffle(T *first, T *last) {
		int n = last - first;
		for (int i = 0; i < n; i++) {
			T *p1 = first + i;
			T *p2 = first + rand_int(i, n - 1);
			int tmp = *p1;
			*p1 = *p2;
			*p2 = tmp;
		}
	}
}

namespace alice_edges {
	const int K = 60;
	const int M = 83;
	const int N = K * M + 2;
	long long weight[N][N];
	int pos[K * M];

	void build() {
		for (int i = 0; i < K; i++) {
			fill(pos + i * M, pos + (i + 1) * M, i);
		}
		alice_rng::shuffle(pos, pos + K * M);
		for (int i = 2; i < N; i++) {
			while (true) {
				int sum = 0;
				for (int j = 0; j < i; j++) {
					weight[i][j] = alice_rng::rand_bits(1);
					sum += weight[i][j];
				}
				if (sum != 0 && sum != i) {
					break;
				}
			}
			alice_rng::shuffle(weight[i], weight[i] + i);
			for (int j = 0; j < i; j++) {
				weight[i][j] <<= pos[i - 2];
			}
		}
	}
}

vector<pair<int, int>> Alice() {
	alice_edges::build();
	long long X = setN(alice_edges::N);
	vector<pair<int, int>> res;
	for (int i = 1; i < alice_edges::N; i++) {
		while (true) {
			int j = alice_rng::rand_int(0, i - 1);
			if ((X & alice_edges::weight[i][j]) == alice_edges::weight[i][j]) {
				res.emplace_back(j + 1, i + 1);
				break;
			}
		}
	}
	return res;
}
#include "Bob.h"
#include <bits/stdc++.h>
using namespace std;

namespace bob_rng {
	unsigned long long state = 88172645463325252LL;
 
	int rand_bit() {
		state ^= (state << 13);
		state ^= (state >> 7);
		state ^= (state << 17);
		return (state & 1);
	}

	long long rand_int(long long l, long long r) {
		long long d = r - l;
		int k = 0;
		while ((1LL << k) <= d) {
			k++;
		}
		while (true) {
			long long x = 0;
			for (int i = 0; i < k; i++) {
				x |= ((long long)rand_bit() << i);
			}
			if (x <= d) {
				return l + x;
			}
		}
	}

	template <typename T>
	void shuffle(T *first, T *last) {
		int n = last - first;
		for (int i = 0; i < n; i++) {
			T *p1 = first + i;
			T *p2 = first + rand_int(i, n - 1);
			int tmp = *p1;
			*p1 = *p2;
			*p2 = tmp;
		}
	}
}

namespace bob_edges {
	const int K = 60;
	const int M = 83;
	const int N = K * M + 2;
	vector<vector<long long>> weight;
 
	void build() {
		weight.resize(N);
		for (int i = 1; i < N; i++) {
			weight[i].resize(i);
		}
		vector<int> pos(K * M);
		for (int i = 0; i < K; i++) {
			fill(pos.begin() + i * M, pos.begin() + (i + 1) * M, i);
		}
		bob_rng::shuffle(pos);
		long double max_p = 0.0L;
		for (int i = 2; i < N; i++) {
			while (true) {
				int sum = 0;
				for (int j = 0; j < i; j++) {
					weight[i][j] = bob_rng::rand_bit();
					sum += weight[i][j];
				}
				if (sum != 0 && sum != i) {
					max_p = max(max_p, 1.0L * max(sum, i - sum) / i);
					break;
				}
			}
			bob_rng::shuffle(weight[i]);
			for (int j = 0; j < i; j++) {
				weight[i][j] <<= pos[i - 2];
			}
		}
	}
}

long long Bob(vector<pair<int, int>> V) {
	bob_edges::build();
	long long res = 0;
	for (auto [j, i]: V) {
		j--;
		i--;
		res |= bob_edges::weight[i][j];
	}
	return res;
}

Compilation message

Bob.cpp: In function 'void bob_edges::build()':
Bob.cpp:60:23: error: no matching function for call to 'shuffle(std::vector<int>&)'
   60 |   bob_rng::shuffle(pos);
      |                       ^
Bob.cpp:33:7: note: candidate: 'template<class T> void bob_rng::shuffle(T*, T*)'
   33 |  void shuffle(T *first, T *last) {
      |       ^~~~~~~
Bob.cpp:33:7: note:   template argument deduction/substitution failed:
Bob.cpp:60:23: note:   mismatched types 'T*' and 'std::vector<int>'
   60 |   bob_rng::shuffle(pos);
      |                       ^
Bob.cpp:74:30: error: no matching function for call to 'shuffle(__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type&)'
   74 |    bob_rng::shuffle(weight[i]);
      |                              ^
Bob.cpp:33:7: note: candidate: 'template<class T> void bob_rng::shuffle(T*, T*)'
   33 |  void shuffle(T *first, T *last) {
      |       ^~~~~~~
Bob.cpp:33:7: note:   template argument deduction/substitution failed:
Bob.cpp:74:30: note:   mismatched types 'T*' and 'std::vector<long long int>'
   74 |    bob_rng::shuffle(weight[i]);
      |                              ^