Submission #29730

#	Time	Username	Problem	Language	Result	Execution time	Memory
29730		cdemirer	Secret (JOI14_secret)	C++14	0 / 100	626 ms	9920 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

int _N;
int _A[1000];
int hesaplar[1000][1000];

void calc(int l, int r) {
	if (l == r) {
		return;
	}
	int mid = (l+r)/2;
	if (r - l == 1) {
		hesaplar[mid][mid+1] = Secret(_A[mid], _A[mid+1]);
		hesaplar[mid+1][mid] = _A[mid];
		return;
	}
	calc(l, mid-1);
	calc(mid+1, r);
	int lmid = (l+mid)/2, rmid = (mid+1+r)/2;
	if (mid-1 > lmid) hesaplar[mid][mid-1] = _A[mid-1];
	for (int i = mid-2; i > lmid; i--) {
		hesaplar[mid][i] = Secret(_A[i], hesaplar[mid][i+1]);
	}
	if (lmid == mid-1) {
		hesaplar[mid][lmid] = _A[lmid];
	}
	else {
		hesaplar[mid][lmid] = Secret(_A[lmid], hesaplar[mid][lmid+1]);
	}
	for (int i = lmid-1; i >= l; i--) {
		//cerr << "A" << endl;
		//cerr << "lmid, i, mid, lmid+1 : " << lmid << " " << i << " " << mid << " " << mid+1 << endl;
		hesaplar[mid][i] = Secret(hesaplar[lmid][i], hesaplar[mid][lmid]);
		//cerr << "B" << endl;
	}
	for (int i = mid+1; i < rmid; i++) {
		hesaplar[mid][i] = Secret(hesaplar[mid][i-1], _A[i]);
	}
	for (int i = rmid; i <= r; i++) {
		hesaplar[mid][i] = Secret(hesaplar[mid][rmid-1], hesaplar[rmid][i]);
	}
}

void Init(int N, int A[]) {
	memset(hesaplar, -1, sizeof(hesaplar));
	_N = N;
	for (int i = 0; i < N; i++) _A[i] = A[i];
	for (int i = 0; i < N; i++) hesaplar[i][i] = _A[i];
	calc(0, _N-1);
}

int Query(int L, int R) {
	int l = 0, r = _N-1;
	while (true) {
		//cerr << l << " " << r << " : " << L << " " << R << endl;
		int mid = (l+r)/2;
		if (L == R && L == mid) return _A[mid];
		else if (L <= mid && R >= mid) {
			int a = hesaplar[mid][L];
			int b = hesaplar[mid][R];
			return Secret(a, b);
		}
		else if (R == mid) {
			return Secret(hesaplar[mid][L], _A[mid]);
		}
		else if (R == mid-1) {
			return hesaplar[mid][L];
		}
		else if (L == mid) {
			return hesaplar[mid][R];
		}
		else if (R < mid) {
			r = mid;
		}
		else if (L > mid) {
			l = mid+1;
		}
		else {
			cerr << "Impossible branch" << endl;
		}
	}
}

• Subtask 1: 0 / 100