oj.uz

Submission #29734

# Submission time Handle Problem Language Result Execution time Memory
29734 2017-07-20T11:50:45 Z cdemirer Secret (JOI14_secret) C++14
0 / 100
 663 ms 9920 KB 
#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-1)/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-1;
		}
		else if (L > mid) {
			l = mid+1;
		}
		else {
			cerr << "Impossible branch" << endl;
		}
	}
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 9920 KB Wrong Answer: Query(255, 409) - expected : 307522235, actual : 38999632.
2 Incorrect 153 ms 9920 KB Wrong Answer: Query(127, 153) - expected : 342921603, actual : 542288066.
3 Incorrect 163 ms 9920 KB Wrong Answer: Query(139, 140) - expected : 532639920, actual : 782809598.
4 Incorrect 603 ms 9920 KB Wrong Answer: Query(374, 396) - expected : 402362963, actual : 342036658.
5 Incorrect 613 ms 9920 KB Wrong Answer: Query(937, 999) - expected : 615241818, actual : 827956544.
6 Incorrect 629 ms 9920 KB Wrong Answer: Query(811, 813) - expected : 25091616, actual : 677845752.
7 Correct 633 ms 9920 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
8 Correct 619 ms 9920 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
9 Correct 646 ms 9920 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
10 Correct 663 ms 9920 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1