oj.uz

답안 #297688

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
297688 2020-09-11T18:28:35 Z penguinhacker 비밀 (JOI14_secret) C++17
100 / 100
 511 ms 4648 KB 
#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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 143 ms 2424 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 144 ms 2424 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
3 Correct 147 ms 2424 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
4 Correct 503 ms 4472 KB Output is correct - number of calls to Secret by Init = 7991, maximum number of calls to Secret by Query = 1
5 Correct 506 ms 4472 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
6 Correct 507 ms 4344 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
7 Correct 510 ms 4648 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
8 Correct 511 ms 4472 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
9 Correct 505 ms 4344 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
10 Correct 504 ms 4344 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1