oj.uz

Submission #375337

# Submission time Handle Problem Language Result Execution time Memory
375337 2021-03-09T09:24:51 Z peijar Secret (JOI14_secret) C++17
0 / 100
 536 ms 8684 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000;
int queries[MAXN][MAXN];
int values[MAXN];
int nbElem;

int calcQueries(int deb, int fin)
// Calcule toutes les requetes [i, (deb+fin)/2] et [(deb+fin)/2+1, i]
{
	if (deb >= fin)
		return 0;
	int mid = (deb + fin) / 2;
	int ret = calcQueries(deb,mid) + calcQueries(mid+1, fin) + fin - deb-1;
	int mid2 = (deb + mid) / 2;
	for (int i(deb); i < mid; ++i)
		if (i <= mid2)
		{
			queries[i][mid] = Secret(queries[i][mid2], queries[mid2+1][mid]);
			ret++;
		}
	int mid3 = (mid + 1 + fin) / 2;
	for (int i(mid+2); i <= fin; ++i)
		if (i > mid3)
		{
			queries[mid+1][i] = Secret(queries[mid+1][mid3], queries[mid3+1][i]);
			ret++;
		}
	return ret;
}

int solve(int deb, int fin, int reqDeb, int reqFin)
{
	if (deb == fin)
		return values[deb];
	int mid = (deb + fin) / 2;
	if (reqFin <= mid)
		return solve(deb, mid, reqDeb, reqFin);
	if (reqDeb > mid)
		return solve(mid+1, fin, reqDeb, reqFin);
	// reqDeb <= mid < reqFin
	return Secret(queries[reqDeb][mid], queries[mid+1][reqFin]);
}

void Init(int N, int A[]) {
	nbElem = N;
	for (int i(0); i < N; ++i)
		values[i] = queries[i][i] = A[i];
	cerr << "nombre de requetes : " << calcQueries(0, N-1) << endl;
}

int Query(int L, int R) {
	return solve(0, nbElem-1, L, R);
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 141 ms 4628 KB Wrong Answer: Query(113, 206) - expected : 536899947, actual : 50593987.
2 Incorrect 136 ms 4504 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 571476064.
3 Incorrect 132 ms 4576 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 553936904.
4 Incorrect 511 ms 8300 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 8389239.
5 Incorrect 507 ms 8428 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 60871936.
6 Incorrect 505 ms 8316 KB Wrong Answer: Query(200, 208) - expected : 277813445, actual : 413361218.
7 Incorrect 536 ms 8532 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 608837705.
8 Incorrect 517 ms 8300 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 549562760.
9 Incorrect 508 ms 8448 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 139857418.
10 Incorrect 496 ms 8684 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 69993927.