Submission #297688

#	Time	Username	Problem	Language	Result	Execution time	Memory
297688		penguinhacker	Secret (JOI14_secret)	C++17	100 / 100	511 ms	4648 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"
using namespace std;

/*int Secret(int a, int b) {
	return a ^ b;
}*/

const int mxN = 1000, mxK = 10;
int n, a[mxN];
int tl[mxN][mxK], tr[mxN][mxK];

void Init(int N, int A[]) {
	n = N;
	for (int i = 0; i < n; ++i) {
		a[i] = A[i];
	}
	for (int j = 1; (1 << j) <= n; ++j) {
		int mask = (1 << j) - 1;
		int temp;
		for (int i = 0; i < n; ++i) {
			if (i % (1 << (j + 1)) < (1 << j)) {
				continue;
			}
			temp = ((i & mask) == 0) ? a[i] : Secret(temp, a[i]);
			tr[i][j] = temp;
		}
		for (int i = n - 1; ~i; --i) {
			if (i % (1 << (j + 1)) >= (1 << j)) {
				continue;
			}
			temp = ((i & mask) == mask || i == n - 1) ? a[i] : Secret(a[i], temp);
			tl[i][j] = temp;
		}
	}
}

int Query(int L, int R) {
	if (L == R) return a[L];
	if (R == L + 1) return Secret(a[L], a[R]);
	int x = 31 - __builtin_clz(L ^ R);
	return Secret(tl[L][x], tr[R][x]);
}

/*int Brute(int L, int R) {
	int ans = a[L];
	for (int i = L + 1; i <= R; ++i) {
		ans = Secret(ans, a[i]);
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	int a[100];
	for (int i = 0; i < 100; ++i) {
		a[i] = rng() % 1000 + 1;
	}
	Init(100, a);
	//for (int i = 0; i < 3; ++i) for (int j = i; j < 3; ++j) cout << i << " " << j << " " << Query(i, j) << "\n";
	for (int i = 0; i < 100; ++i) {
		for (int j = i; j < 100; ++j) {
			if (Brute(i, j) != Query(i, j)) {
				cout << i << " " << j << "\n";
				return 0;
			}
		}
	}
	return 0;
}*/

Compilation message (stderr)

secret.cpp: In function 'void Init(int, int*)':
secret.cpp:25:44: warning: 'temp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   25 |    temp = ((i & mask) == 0) ? a[i] : Secret(temp, a[i]);
      |                                      ~~~~~~^~~~~~~~~~~~

• Subtask 1: 100 / 100